0ms | Beats 100.00% | Using Trie | Efficient, Easy & Simple C++ Solution | Full Explained
Advantages of Using Trie
Fast prefix checks, especially for multiple queries or overlapping prefixes.
Efficient memory usage for storing common prefixes across
# Advantages of Using Trie
- Fast prefix checks, especially for multiple queries or overlapping prefixes.
- Efficient memory usage for storing common prefixes across words.

# Intuition 
The solution leverages the Trie data structure to efficiently handle prefix-based operations. Tries are particularly useful when we need to perform repeated prefix queries, as they allow searching in 𝑂(𝑝) time, where 𝑝 is the length of the prefix.
Here:
- Insertion of the prefix into the Trie ensures that we have a quick way to validate prefixes.
- The `start_with` function traverses the Trie to check if any word starts with the given prefix.
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach 
1. Trie Construction:

- A `Trie` node is implemented with `next `pointers for the 26 lowercase English letters and a boolean `isEnd` to mark the end of a word.
- The `insert` function adds the prefix pref to the Trie.
2. Prefix Validation:

- The `start_with `function checks if the current word starts with the inserted prefix by traversing the Trie.
- The traversal stops as soon as we detect the prefix (`isEnd` is true), reducing unnecessary checks.
3. Counting Matches:
- Iterate through all words in `words` and count those that start with the given prefix using the `start_with` function.

<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity: O(p+n⋅w)
Since` 𝑝≪𝑛` in most scenarios, the overall complexity can be approximated to **𝑂(𝑛⋅𝑤)**, which aligns with linear traversal of all words.
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:O(p⋅N)≈O(p)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
const int N=26;
struct Trie {
    Trie* next[N];
    bool isEnd = 0;
    Trie() {
        fill(next, next+N, (Trie*)NULL);
    }
    ~Trie() {
        for (int i=0; i<N; ++i) {
            if (next[i] !=NULL) {
                delete next[i];
            }
        }
    }
    void insert(string& word) {
        Trie* Node=this;
        for(char c: word){
            int i=c-'a';
            if(Node->next[i]==NULL)
                Node->next[i]=new Trie();
            Node=Node->next[i];
        }
        Node->isEnd=1;
    }
};
class Solution {
public:
    Trie trie;
    bool start_with(string& w){
        Trie* Node=&trie;
        for( char c: w){
            int i=c-'a';
            if (Node->next[i]==NULL) return 0;
            Node=Node->next[i];
            if (Node->isEnd) return 1;
        }
        return 0;
    }
    int prefixCount(vector<string>& words, string& pref) {
        trie.insert(pref);
        int cnt=0;
        for(string& w: words)
            cnt+=start_with(w);
        return cnt;
    }
};
```
['Array', 'Two Pointers', 'String', 'Dynamic Programming', 'Trie', 'Recursion', 'Suffix Array', 'String Matching', 'Prefix Sum', 'C++']