Problem statement

https://leetcode.com/problems/number-of-matching-subsequences/

Solution

This problem is extension of problem 392 Is Subsequence, but here we have several patterns we need to find.

Let 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.

Complexity

Time 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).

Code

class Solution:
    def numMatchingSubseq(self, S, words):
        def isSubseq(word):
            curr = 0
            for symbol in word:
                ind = bisect_left(places[symbol], curr)
                if ind >= len(places[symbol]):
                    return False
                curr = places[symbol][ind] + 1
            
            return True
        
        places = defaultdict(list)
        for i, symbol in enumerate(S):
            places[symbol].append(i)
        
        return sum(isSubseq(word) for word in words)