DFS on the Trie of the words
Create a Trie of all the words, keeps track of the repeated words.\nDo a DFS on the Trie, and for each children check if the current child (character) exists in
Create a Trie of all the words, keeps track of the repeated words.\nDo a DFS on the Trie, and for each children check if the current child (character) exists in the string S (based on the current index)\n```\n\nstruct TrieNode {\n    unordered_map<char, TrieNode*> children;\n    bool isEnd;\n    int count; // numbers of the same word in the dict\n    TrieNode() { isEnd = false; count = 0;}\n};\n\nclass Trie {\n    public:\n    TrieNode* root;\n    Trie() { root = new TrieNode(); }\n    void insert(string s) {\n        TrieNode* it = root;\n        for(char c : s) {\n            if(it->children.count(c) == 0)\n                it->children[c] = new TrieNode();\n            it = it->children[c];\n        }\n        it->isEnd = true;\n        it->count++; // in case we have repeated words\n    }\n   \n};\n\nclass Solution {\n    int ans = 0;\n    int findIndex(const string &s, int start, char c) {\n        for(int i = start; i < s.size(); i++)\n            if(s[i] == c) return i;\n        return -1;\n    }\n    \n    // DFS on the Trie\n    void dfs(const string& s, TrieNode* node, int start) {\n        for(auto p : node->children) {\n            int idx = findIndex(s, start, p.first);\n            if(idx != -1) {\n                if(p.second->isEnd) ans+= p.second->count;\n                dfs(s, p.second, idx + 1);\n            }\n                \n        }\n    }\npublic:\n    int numMatchingSubseq(string s, vector<string>& words) {\n        Trie trie;\n        for(string w : words)\n            trie.insert(w);\n        \n        dfs(s, trie.root, 0);\n        return ans;\n    }\n};\n```
['Depth-First Search', 'Trie', 'C']