[Python] binary search solution, explained
This problem is extension of problem 392 Is Subsequence, but here we have several patterns we need to find.\n\nLet n be length of s and m be total length of all
This problem is extension of problem **392 Is Subsequence**, but here we have several patterns we need to find.\n\nLet `n` be length of `s` and `m` be total length of all words in words.  Then we can precompute all places for each symbol in `s` and then use binary search to find if word. \n\n#### Complexity\nTime complexity is `O(m*log n + n)`, because we do at most `m` binary searches and we need `O(n)` to evaluate `places`.  Space complexity is `O(n)`.\n\n#### Code\n```python\nclass Solution:\n    def numMatchingSubseq(self, S, words):\n        def isSubseq(word):\n            curr = 0\n            for symbol in word:\n                ind = bisect_left(places[symbol], curr)\n                if ind >= len(places[symbol]):\n                    return False\n                curr = places[symbol][ind] + 1\n            \n            return True\n        \n        places = defaultdict(list)\n        for i, symbol in enumerate(S):\n            places[symbol].append(i)\n        \n        return sum(isSubseq(word) for word in words)\n```\n\nIf you have any question, feel free to ask. If you like the explanations, please **Upvote!**
['Binary Search']