<p>Given a string <code>s</code> and an array of strings <code>words</code>, return <em>the number of</em> <code>words[i]</code> <em>that is a subsequence of</em> <code>s</code>.</p>

<p>A <strong>subsequence</strong> of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.</p>

<ul>
	<li>For example, <code>&quot;ace&quot;</code> is a subsequence of <code>&quot;abcde&quot;</code>.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;abcde&quot;, words = [&quot;a&quot;,&quot;bb&quot;,&quot;acd&quot;,&quot;ace&quot;]
<strong>Output:</strong> 3
<strong>Explanation:</strong> There are three strings in words that are a subsequence of s: &quot;a&quot;, &quot;acd&quot;, &quot;ace&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;dsahjpjauf&quot;, words = [&quot;ahjpjau&quot;,&quot;ja&quot;,&quot;ahbwzgqnuk&quot;,&quot;tnmlanowax&quot;]
<strong>Output:</strong> 2
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= words.length &lt;= 5000</code></li>
	<li><code>1 &lt;= words[i].length &lt;= 50</code></li>
	<li><code>s</code> and <code>words[i]</code> consist of only lowercase English letters.</li>
</ul>

// struct Node{
//     Node* links[26];
//     bool flag = false;

//     bool containsKey(char ch)
//     {
//         return (links[ch-'a']!=NULL);
//     }

//     void put(char ch, Node* node)
//     {
//         links[ch-'a'] = node;
//     }

//     Node* get(char ch)
//     {
//         return links[ch-'a'];
//     }

//     void setEnd()
//     {
//         flag = true;
//     }

//     bool isEnd()
//     {
//         return flag;
//     }
// };

// class Trie{
// private:
//     Node* root;

// public:
//     Trie()
//     {
//         root = new Node();
//     }

//     void insert(string word)
//     {
//         Node* node = root;

//         for(int i=0; i<word.size(); i++)
//         {
//             if(!node->containsKey(word[i])) node->put(word[i], new Node());
//             node = node->get(word[i]);
//         }
//         node->setEnd();
//     }

//     bool search(string word)
//     {
//         Node* node = root;

//         for(int i=0; i<word.size(); i++)
//         {
//             if(node==root || node->isEnd()) node = node->get(word[i]);
//             else return false;
//         }
//         return true;
//     }
// };

// class Solution {
// public:
//     vector<string> subSet(string &s, int i, string& sub, vector<string>& ans)
//     {
//         ans.push_back(sub);

//         for(int j =i; j<s.size(); j++)
//         {
//             sub+=s[i];
//             subSet(s, j + 1, sub, ans);
//             sub.pop_back();
//         }

//         return ans;
//     }

//     int numMatchingSubseq(string s, vector<string>& words) {
//         int n = words.size();
//         Trie trie;

//         for(int i=0; i<n; i++)
//         {
//             trie.insert(words[i]);
//         }

//         vector<string>ans;
//         string sub;
//         ans = subSet(s,0,sub,ans);

//         int cnt=0;
//         for(auto it : ans)
//         {
//             if(trie.search(it)) cnt++;
//         }
//         return cnt;
//     }
// };


/* 
    Time: O(n*p*logm) | m=s.length | n=words.length | p=words[i].length
    Space: O(n*p)
    Tag: Trie, String, DFS, Hashing
    Difficulty: H
*/

class Node {
public:
    int isTerminal;
    vector<Node *> children;
    Node() {
        children.resize(26, NULL);
        isTerminal = 0;
    }
};

class Trie {

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

    Node *root;
    void insert(string s) {
        Node *cur = root;
        for (char ch : s) {
            if (!cur->children[ch - 'a']) cur->children[ch - 'a'] = new Node();
            cur = cur->children[ch - 'a'];
        }
        (cur->isTerminal)++;
    }

    int dfs(Node *root, string &s, int idx, vector<int>pos[]) {
        int res = 0;
        for (int i = 0; i < 26; i++) {
            if (root->children[i]) {
                int newIdx = upper_bound(pos[i].begin(), pos[i].end(), idx) - pos[i].begin();
                if (newIdx == pos[i].size()) continue;
                res += dfs(root->children[i], s, pos[i][newIdx], pos);
            }
        }
        return res + root->isTerminal;
    }
};

class Solution {
public:
    int numMatchingSubseq(string s, vector<string> &words) {
        Trie *t = new Trie;
        for (string str : words) {
            t->insert(str);
        }
        vector<int> pos[26];
        for (int i = 0; i < s.length(); i++) {
            pos[s[i] - 'a'].push_back(i);
        }
        return t->dfs(t->root, s, -1, pos);
    }
};
359014