Simple | Trie ->2 Approach Detailed Explanation
🌟 Count Prefix MatchesIn this problem, you are given an array of strings words and a string pref. The task is to return the number of strings in words that cont
# 🌟 Count Prefix Matches

In this problem, you are given an array of strings `words` and a string `pref`. The task is to return the number of strings in `words` that contain `pref` as a prefix. A **prefix** refers to the beginning part of a string.

# Channel https://www.youtube.com/@Sumeet_Sharma-1 #
# Telegram https://t.me/leetmath #

# 10 jan Simple Solution : [SOlUTION](https://leetcode.com/problems/word-subsets/solutions/6257553/memset-max-freq-detailed-explanation-solution/) #

---

## 🧠 Intuition
A **prefix** is the starting substring of a given string. To solve the problem:
1. We will iterate through the list of strings in `words`.
2. For each string, we will check if it starts with the given prefix `pref`.
3. We will count how many strings in the array match the prefix condition.

### Example:
- For the string `"pay"` and the prefix `"at"`, we check if `"pay"` starts with `"at"`. It does NOt , so it's not a match.
- For the string `"attention"` and the prefix `"at"`, we check if `"attention"` starts with `"at"`. It does, so it's a match.
- For the string `"practice"` and the prefix `"at"`, we check if `"practice"` starts with `"at"`. It does NOt , so it's not a match.
- For the string `"attend"` and the prefix `"at"`, we check if `"attend"` starts with `"at"`. It does, so it's a match.
![Screenshot 2025-01-09 082841.png](https://assets.leetcode.com/users/images/b166cb38-6dbd-4c51-a36c-4464e6ba5c0b_1736391553.0079782.png)


---

## 🛠️ Approach

Here’s how to approach solving the problem step-by-step:

1. **Iterate Through the Array**:
   - Loop through each string in the `words` array.
   
2. **Check for Prefix**:
   - For each string, check if it starts with the given prefix `pref`.
   - In Python, you can use the built-in method `startswith()`. Other languages have similar methods or you can manually compare the first characters.
   
3. **Count Matches**:
   - Maintain a counter variable to track how many words start with the prefix `pref`.
   - Every time a match is found, increment the counter by 1.

4. **Return Result**:
   - After checking all words, return the final count of prefix matches.

---

## 📊 Complexity

### Time Complexity:
- **O(n * m)**  
  - \(n\) is the number of words in the array.
  - \(m\) is the average length of each word.
  - For each word, checking the prefix using `startswith()` takes \(O(m)\) time.

### Space Complexity:
- **O(1)**  
  - We only use a counter variable for storing the result, so the space complexity is constant.

---

![9c6f9412-c860-47d6-9a2e-7fcf37ff3321_1686334926.180891.png](https://assets.leetcode.com/users/images/7bef5edb-22b2-44df-862d-4f0a3ad31c2a_1736381622.5732725.png)


# Code
```cpp []
class Solution {
public:
    int prefixCount(vector<string>& words, string pref) {
        int count = 0;
    for (const string& word : words) {
        if (word.find(pref) == 0) { 
            count++;
        }
    }
    return count;
    }
};
```
```Java []
class Solution {
    public int prefixCount(String[] words, String pref) {
        int count = 0;
        for (String word : words) {
            if (word.startsWith(pref)) {
                count++;
            }
        }
        return count;
    }
}
```
```Python []
class Solution:
    def prefixCount(self, words: List[str], pref: str) -> int:
        count = 0
        for word in words:
            if word.startswith(pref):
                count += 1
        return count
```
```C []
int prefixCount(char** words, int wordsSize, char* pref) {
    int count = 0;
    for (int i = 0; i < wordsSize; i++) {
        if (strncmp(words[i], pref, strlen(pref)) == 0) {
            count++;
        }
    }
    return count;
}
```
```C# []
public class Solution {
    public int PrefixCount(string[] words, string pref) {
        int count = 0;
        foreach (string word in words) {
            if (word.StartsWith(pref)) {
                count++;
            }
        }
        return count;
    }
}
```
```Javascript []
/**
 * @param {string[]} words
 * @param {string} pref
 * @return {number}
 */
var prefixCount = function(words, pref) {
    let count = 0;
    for (let word of words) {
        if (word.startsWith(pref)) {
            count++;
        }
    }
    return count;
};
```
# Trie Aproch #
```C++ []
class Node {
public:
    Node* children[26];
    int count;

    Node() {
        for (int i = 0; i < 26; i++) {
            children[i] = nullptr;
        }
        count = 0;
    }
};

class PrefixTree {
private:
    Node* root;

public:
    PrefixTree() {
        root = new Node();
    }

    void addWord(const string& word) {
        Node* current = root;
        for (char ch : word) {
            int index = ch - 'a';
            if (current->children[index] == nullptr) {
                current->children[index] = new Node();
            }
            current = current->children[index];
            current->count++;
        }
    }

    int getPrefixCount(const string& prefix) {
        Node* current = root;
        for (char ch : prefix) {
            int index = ch - 'a';
            if (current->children[index] == nullptr) {
                return 0;
            }
            current = current->children[index];
        }
        return current->count;
    }
};

class Solution {
public:
    int prefixCount(vector<string>& words, string prefix) {
        PrefixTree tree;
        for (const string& word : words) {
            tree.addWord(word);
        }
        return tree.getPrefixCount(prefix);
    }
};
```
['Trie', 'C', 'String Matching', 'C++', 'Java', 'Python3', 'JavaScript', 'C#']