# Count Prefixes of a Given String
**Difficulty:** EASY
[External](https://leetcode.com/problems/count-prefixes-of-a-given-string)
Canonical: https://scaleengineer.com/dsa/problems/count-prefixes-of-a-given-string
**Data structures:** Array, String
---
## Problem
You are given a string array `words` and a string `s`, where `words[i]` and `s` comprise only of **lowercase English letters**.

Return _the **number of strings** in_ `words` _that are a **prefix** of_ `s`.

A **prefix** of a string is a substring that occurs at the beginning of the string. A **substring** is a contiguous sequence of characters within a string.

**Example 1:**

**Input:** words = ["a","b","c","ab","bc","abc"], s = "abc"
**Output:** 3
**Explanation:**
The strings in words which are a prefix of s = "abc" are:
"a", "ab", and "abc".
Thus the number of strings in words which are a prefix of s is 3.

**Example 2:**

**Input:** words = ["a","a"], s = "aa"
**Output:** 2
**Explanation:**
Both of the strings are a prefix of s. 
Note that the same string can occur multiple times in words, and it should be counted each time.

**Constraints:**

* `1 <= words.length <= 1000`
* `1 <= words[i].length, s.length <= 10`
* `words[i]` and `s` consist of lowercase English letters **only**.

# Approaches
## Brute-Force Iteration
This approach iterates through each word in the input array `words` and checks if it is a prefix of the string `s`. A simple counter is used to keep track of the number of words that satisfy this condition.
**Time:** O(N * L), where `N` is the number of words in the `words` array and `L` is the maximum length of a word. For each of the `N` words, the `startsWith` check takes up to `O(L)` time. · **Space:** O(1), as we only use a single integer variable for the counter, requiring constant extra space.
**Pros:** Very simple to understand and implement.; Highly efficient in terms of space complexity.; For the given constraints, it's fast enough and might even outperform more complex solutions due to lower overhead.
**Cons:** Can be inefficient if the number of words (`N`) or the length of the words (`L`) is very large.; It repeatedly scans the beginning of string `s` for each word, which involves redundant comparisons if many words share common prefixes.
### Explanation
We initialize a counter variable, `prefixCount`, to zero. We then loop through every `word` in the `words` array. For each `word`, we can use the built-in `startsWith()` method of the `String` class to check if `s` begins with that `word`. The `s.startsWith(word)` method efficiently compares the characters of `word` with the beginning characters of `s`. If `s.startsWith(word)` returns `true`, it means `word` is a prefix of `s`, and we increment `prefixCount`. After checking all the words in the array, the final value of `prefixCount` is the answer. This method is straightforward to implement and understand, and given the problem's constraints, it is perfectly acceptable.

```java
class Solution {
    public int countPrefixes(String[] words, String s) {
        int count = 0;
        for (String word : words) {
            if (s.startsWith(word)) {
                count++;
            }
        }
        return count;
    }
}
```
### Algorithm
- 1. Initialize an integer variable `count` to 0.
- 2. Iterate through each `string` in the `words` array.
- 3. For each `string`, check if `s` starts with it using the built-in `s.startsWith(string)` method.
- 4. If the check returns `true`, it means the current string is a prefix of `s`, so increment `count`.
- 5. After the loop finishes, return the final `count`.

## Optimized Approach using Trie (Prefix Tree)
This approach uses a Trie (also known as a prefix tree) to optimize the process. First, all words from the `words` array are inserted into the Trie. Then, we traverse the string `s` on the Trie and sum up the counts of all words that form a prefix of `s`.
**Time:** O(W + M), where `W` is the total number of characters in all words in the `words` array, and `M` is the length of `s`. Building the Trie takes `O(W)` time. Traversing `s` on the Trie takes `O(M)` time. · **Space:** O(W), where `W` is the total number of characters in all words in the `words` array. In the worst case, the Trie will have a distinct node for each character of each word (if there are no shared prefixes).
**Pros:** Very efficient for problems with many prefix-based queries on the same set of words, as the build time is a one-time cost.; Avoids redundant comparisons by structuring the words in a prefix-based hierarchy.
**Cons:** Higher implementation complexity compared to the brute-force approach.; Consumes more memory due to the Trie data structure. For this specific problem with its small constraints and a single query, the space overhead might not be justified.
### Explanation
A Trie is a specialized tree data structure for storing strings, where each node represents a character and paths from the root represent prefixes. First, we define a `TrieNode` class. Each node contains an array of children (one for each letter of the alphabet) and a counter, say `count`, to store how many words from the input array end at this node. We build the Trie by iterating through each `word` in the `words` array and inserting it. The insertion process involves traversing the Trie from the root, creating new nodes as necessary for each character in the word. When we reach the end of a word, we increment the `count` at the final node. After building the Trie, we traverse the string `s` character by character, starting from the Trie's root. For each prefix of `s` (i.e., `s.substring(0, i+1)`), we check the corresponding node in the Trie. The `count` at this node tells us how many words in the original array are exactly equal to this prefix. We sum up these counts for all prefixes of `s` to get the total.

```java
class TrieNode {
    TrieNode[] children;
    int count; // Number of words ending at this node

    public TrieNode() {
        children = new TrieNode[26];
        count = 0;
    }
}

class Solution {
    public int countPrefixes(String[] words, String s) {
        TrieNode root = new TrieNode();
        // Build the Trie
        for (String word : words) {
            TrieNode curr = root;
            for (char c : word.toCharArray()) {
                if (curr.children[c - 'a'] == null) {
                    curr.children[c - 'a'] = new TrieNode();
                }
                curr = curr.children[c - 'a'];
            }
            curr.count++;
        }

        int totalPrefixes = 0;
        TrieNode curr = root;
        // Traverse s on the Trie and count prefixes
        for (char c : s.toCharArray()) {
            if (curr.children[c - 'a'] == null) {
                break; // No more prefixes of s exist in the Trie
            }
            curr = curr.children[c - 'a'];
            totalPrefixes += curr.count; // Add all words that are equal to the current prefix of s
        }
        return totalPrefixes;
    }
}
```
### Algorithm
- 1. Define a `TrieNode` class with `children` (an array of 26 `TrieNode`s) and an integer `count` to track how many words end at this node.
- 2. Create a `root` `TrieNode`.
- 3. **Build Phase**: Iterate through each `word` in the `words` array.
- 4. For each `word`, traverse the Trie from the `root`, character by character, creating new nodes if they don't exist.
- 5. At the node corresponding to the last character of the `word`, increment its `count`.
- 6. **Counting Phase**: Initialize `totalCount` to 0 and a `currentNode` to `root`.
- 7. Iterate through each character `c` of the string `s`.
- 8. Move `currentNode` to its child corresponding to `c`.
- 9. If the child node is `null` at any point, it means no more prefixes of `s` can be found, so break the loop.
- 10. Add the `count` of the `currentNode` to `totalCount`. This `count` represents the number of words that are identical to the current prefix of `s`.
- 11. After iterating through `s`, return `totalCount`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int CountPrefixes(string[] words, string s) {
        return words.Count(w => s.StartsWith(w));
    }
}
```

### Java

```java
class Solution { public int countPrefixes ( String [] words , String s ) { int ans = 0 ; for ( String w : words ) { if ( s . startsWith ( w )) { ++ ans ; } } return ans ; } }
```

### CPP

```cpp
class Solution { public: int countPrefixes ( vector < string >& words , string s ) { int ans = 0 ; for ( auto & w : words ) { ans += s . starts_with ( w ); } return ans ; } };
```

### Python

```python
class Solution : def countPrefixes ( self , words : List [ str ], s : str ) -> int : return sum ( s . startswith ( w ) for w in words )
```