1-liner vs Trie||C++ Py3 beats 100%
IntuitionProvide 2 approaches
1 is 1-liner using starts_with
other is using Trie.
C++ & Python are done.Approach
1st C++ uses accumulate applying for words, wit
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Provide 2 approaches
1 is 1-liner using starts_with
other is using Trie.
C++ & Python are done.
# Approach
<!-- Describe your approach to solving the problem. -->
1. 1st C++ uses `accumulat`e applying for `words`, with a lambda defined by
```
[pref](int sum, auto& w){
    return sum+=w.starts_with(pref);
});
```
2. 2nd approach is using Trie.
3. The Trie solution has the similar process like 1st C++. Insert only `pref` in the Trie trie; define `start_with` function
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
$O(|pref|+\sum_{w\in words}|w|)$
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
1-liner: $O(1)$
Trie: $O(|pref|)$
# Code || C++ , Python 1-liner 0ms beats 100%
```cpp []
class Solution {
public:
    int prefixCount(vector<string>& words, string& pref) {
        return accumulate(words.begin(), words.end(), 0,
        [pref](int sum, auto& w){
            return sum+=w.starts_with(pref);
        });
    }
};
```
```Python []
class Solution:
    def prefixCount(self, words: List[str], pref: str) -> int:
        return sum(w.startswith(pref) for w in words)
        
```
# Code using Trie||0ms beats 100%
```
// struct Trie for N alphabets
const int N=26;
struct Trie {
    Trie* next[N];
    bool isEnd = 0;

    Trie() {
        fill(next, next+N, (Trie*)NULL);
    }

    ~Trie() {
    //    cout<<"Destructor\n";
        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;
    }
};
```
# Trie is an advanced data structure. Using it one can solve many problems
[[Leetcode 140. Word Break II](https://leetcode.com/problems/word-break-ii/solutions/5203799/dp-hash-vs-dp-trie-0ms-beats-100/) Please turn on English subtitles if necessary]
[https://youtu.be/_E-fcmVmkYU?si=Ve6Z8zuPIi08k0VI](https://youtu.be/_E-fcmVmkYU?si=Ve6Z8zuPIi08k0VI)

['Trie', 'String Matching', 'C++', 'Python3']