# Counting Words With a Given Prefix
**Difficulty:** EASY
[External](https://leetcode.com/problems/counting-words-with-a-given-prefix)
Canonical: https://scaleengineer.com/dsa/problems/counting-words-with-a-given-prefix
**Patterns:** [String Matching](https://scaleengineer.com/dsa/patterns/string-matching)
**Data structures:** Array, String
**Companies:** [DoorDash](https://scaleengineer.com/companies/doordash)
---
## Problem
You are given an array of strings `words` and a string `pref`.

Return _the number of strings in_ `words` _that contain_ `pref` _as a **prefix**_.

A **prefix** of a string `s` is any leading contiguous substring of `s`.

**Example 1:**

**Input:** words = ["pay","**at**tention","practice","**at**tend"], `pref `= "at"
**Output:** 2
**Explanation:** The 2 strings that contain "at" as a prefix are: "**at**tention" and "**at**tend".

**Example 2:**

**Input:** words = ["leetcode","win","loops","success"], `pref `= "code"
**Output:** 0
**Explanation:** There are no strings that contain "code" as a prefix.

**Constraints:**

* `1 <= words.length <= 100`
* `1 <= words[i].length, pref.length <= 100`
* `words[i]` and `pref` consist of lowercase English letters.

# Approaches
## Trie (Prefix Tree) Approach
This approach involves building a Trie (also known as a prefix tree) from all the words in the input array. A Trie is a tree-like data structure that stores strings, where each node represents a character and paths from the root to a node represent prefixes. After building the Trie, we can efficiently search for the given prefix.
**Time:** O(S + M), where S is the total number of characters in all words and M is the length of the prefix. It takes O(S) time to build the Trie and O(M) time to search for the prefix. · **Space:** O(S), where S is the total number of characters in all words in the array. In the worst case, where no words share prefixes, the space required is proportional to the sum of the lengths of all words.
**Pros:** Extremely fast for multiple queries on the same dataset after the initial build.
**Cons:** High initial setup cost (time and space) for building the Trie, making it inefficient for a single query.; More complex to implement compared to a simple loop.
### Explanation
First, we define a `TrieNode` class. Each node will contain an array of children (one for each letter of the alphabet) and a counter, `count`, to track how many words pass through this node.

We then build the Trie. We iterate through each `word` in the `words` array. For each word, we traverse the Trie from the root, creating new nodes as necessary. At each node along the path for the word, we increment its `count`.

After the Trie is built, we search for the prefix `pref`. We traverse the Trie according to the characters in `pref`.

If we can successfully traverse the entire prefix, the `count` at the final node gives us the number of words that start with `pref`.

If at any point during the traversal we find that a path for a character does not exist, it means no word has this prefix, so we can immediately return 0.

This approach is highly efficient if you need to perform many prefix searches on the same set of words, as the expensive part (building the Trie) is done only once. However, for a single search as required by this problem, the overhead of building the Trie makes it less efficient than a simple linear scan.

```java
class TrieNode {
    TrieNode[] children;
    int count;

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

class Solution {
    public int prefixCount(String[] words, String pref) {
        TrieNode root = new TrieNode();

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

        // Search for the prefix
        TrieNode curr = root;
        for (char c : pref.toCharArray()) {
            int index = c - 'a';
            if (curr.children[index] == null) {
                return 0; // Prefix not found
            }
            curr = curr.children[index];
        }

        return curr.count;
    }
}
```
### Algorithm
- Create a `TrieNode` class with `children` (an array of `TrieNode`s of size 26) and an integer `count` to track how many words pass through or end at this node.
- Initialize a root `TrieNode`.
- For each `word` in the `words` array, insert it into the Trie:
    - Start from the `root`.
    - For each character `c` in the `word`:
        - Find the corresponding child node. If it doesn't exist, create it.
        - Move to the child node.
        - Increment the `count` of the child node.
- To find the number of words with the given prefix `pref`:
    - Start from the `root`.
    - Traverse the Trie according to the characters in `pref`.
    - If at any point a character does not have a corresponding child node, it means no word has this prefix, so return 0.
    - If the traversal is successful, the `count` of the final node reached is the answer.

## Iteration with Manual Prefix Check
This approach iterates through each word in the input array and manually checks if it starts with the given prefix. This avoids using built-in string methods and implements the logic from scratch by comparing characters one by one.
**Time:** O(N * M), where N is the number of words and M is the length of the prefix. We iterate through N words, and for each word, we perform up to M character comparisons. · **Space:** O(1), as we only use a few variables to store the count and loop indices.
**Pros:** Simple to understand and implement without relying on library functions.; Efficient in terms of space.
**Cons:** More verbose than using a built-in method.; Re-implements functionality that is already available and likely optimized in the standard library.
### Explanation
We initialize a counter variable `count` to zero. We loop through every `word` in the `words` array.

For each `word`, we first check if its length is less than the prefix's length. If it is, the word cannot possibly have `pref` as a prefix, so we skip to the next word.

If the word is long enough, we proceed to compare it with the prefix character by character. We can use an inner loop for this. We iterate from the first character up to the length of the prefix. In each iteration, we compare the character from the `word` with the corresponding character from `pref`.

If we find any mismatch, we know it's not a prefix, and we can stop checking this word and move to the next one.

If the inner loop completes without finding any mismatches, it means the word starts with the prefix. We then increment our `count`.

After checking all the words, the final `count` is our answer.

```java
class Solution {
    public int prefixCount(String[] words, String pref) {
        int count = 0;
        int prefLen = pref.length();
        for (String word : words) {
            if (word.length() >= prefLen) {
                boolean match = true;
                for (int i = 0; i < prefLen; i++) {
                    if (word.charAt(i) != pref.charAt(i)) {
                        match = false;
                        break;
                    }
                }
                if (match) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize `count = 0`.
- Get the length of the prefix, `prefLen`.
- For each `word` in the `words` array:
    - First, check if `word.length()` is less than `prefLen`. If it is, continue to the next word.
    - If the word is long enough, assume it's a match by setting a flag `isPrefix = true`.
    - Loop from `i = 0` to `prefLen - 1`:
        - Compare `word.charAt(i)` with `pref.charAt(i)`.
        - If the characters do not match, set `isPrefix = false` and break the inner loop.
    - After the inner loop, if `isPrefix` is still `true`, increment `count`.
- Return `count`.

## Iteration with Built-in `startsWith` Method
This is the most straightforward and idiomatic approach. It involves iterating through the array of words and using the built-in `startsWith()` method provided by the `String` class in Java to check for the prefix.
**Time:** O(N * M), where N is the number of words and M is the length of the prefix. The `startsWith` method takes O(M) time, and we call it for N words. · **Space:** O(1), as we only use a single integer for the counter.
**Pros:** Most concise, readable, and idiomatic solution.; Leverages optimized standard library functions.; Optimal time and space complexity for a single prefix search.
**Cons:** For this specific problem context, there are no significant disadvantages.
### Explanation
The algorithm is very simple. We initialize a counter `count` to 0.

We then iterate through each `word` in the `words` array.

For each `word`, we call `word.startsWith(pref)`. This method returns `true` if the `word` begins with the specified `pref` string, and `false` otherwise.

If the method returns `true`, we increment our `count`.

After the loop has finished checking all the words, the value of `count` is the total number of words that have `pref` as a prefix, which we then return.

This approach is not only concise and easy to read but also leverages the optimized implementation of the standard library. For a single query, this is the most efficient solution.

```java
class Solution {
    public int prefixCount(String[] words, String pref) {
        int count = 0;
        for (String word : words) {
            if (word.startsWith(pref)) {
                count++;
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- For each `word` in the `words` array:
    - Use the built-in `startsWith()` method to check if `word.startsWith(pref)` is true.
    - If it is true, increment `count`.
- After iterating through all the words, return `count`.

# Solutions
### Java

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

```

### Python

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

```

### CPP

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

```