[Python] 2 Solutions with Explanations
Solution 1 is based on https://leetcode.com/problems/number-of-matching-subsequences/discuss/117634/Efficient-and-simple-go-through-words-in-parallel-with-expla
1. Solution 1 is based on https://leetcode.com/problems/number-of-matching-subsequences/discuss/117634/Efficient-and-simple-go-through-words-in-parallel-with-explanation.\n2. For looking up `iter` in Python, please look at: *** Python | iter() method\n3. This problem is highly related to https://leetcode.com/problems/is-subsequence/\n\n**Solution 1**:  Two Pointers\nThe diagram is the visual representation of what the code does with the given Example.\n![image](https://assets.leetcode.com/users/codingasiangirll/image_1586904310.png)\n**Explanation:** `heads` is a dictionary(char, list of iter) as shown in the diagram. Then, we traverse through `S`. Everytime if the `c` in `S` are also presented in `heads`, we iterate through the list of iter to move forward `itr` and put the following to the corresponding character in `heads`. For Example, in the diagram,  if `c == "c"` and `next(itr, None) == d`, `heads["d"]` will append the iterater that points to the next items of `"d"`. Hence, we will get a new (key, value) = (`"d", [itr points to None]`).\n```\nclass Solution:\n    def numMatchingSubseq(self, S: str, words: List[str]) -> int:\n        heads = collections.defaultdict(list)\n        for w in words:\n            heads[w[0]].append(iter(w[1:]))\n        for c in S:\n            if c in heads:\n                for itr in heads.pop(c):\n                    heads[next(itr, None)].append(itr)\n        return len(heads[None])\n```\n\n**Complexity**: \n* Time: O(N+M). N is the length of S, and M is the sum of `words`\'s length.\n* Space: O(M)\n\n**Solution 2**: Binary Search\n**Explanation:** Build a dictionary `lookup` that will store (char,  list of index where char is at in S). Then, we run through the `words`. For each `c` in `word`, we use binary search to find out where `prev` can be inserted (i.e. `index`). `word` would be a valid subsequence of S iff all `prev` can find a bigger `index` in `lookup[c]`. \n```\nclass Solution:\n    def numMatchingSubseq(self, S: str, words: List[str]) -> int:\n        def isSubseq(word):\n            prev = -1\n            for c in word:\n                if c not in lookup: return False\n                index = bisect.bisect(lookup[c], prev)\n                if index >= len(lookup[c]): return False\n                prev = lookup[c][index]\n            return True\n\n        lookup = collections.defaultdict(list)\n        for i, c in enumerate(S):\n            lookup[c].append(i)\n        return sum([1 for word in words if isSubseq(word)])\n```\n\n**Complexity**: \n* Time: O(N+M). N is the length of S, and M is the sum of `words`\'s length.\n* Space: O(N)
['Two Pointers', 'Binary Search']