LC 792

Solution to LeetCode 792 Number of Matching Subsequences.

LeetCode 792

Number of Matching Subsequences (Medium) [link]

Time complexity O(S) + O(W*L*log(S)), space complexity O(S). S is the length of given ‘s’, W is the length of word list ‘words’, L is the length of each word.

# import bisect
class Solution(object):
    def numMatchingSubseq(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: int
        """
        m = {} # there might be duplicates in 'words'
        dictionary = {chr(i + ord('a')) : [] for i in range(26)} # a dict for 26 characters
        for i, char in enumerate(s): # add index of each char in 's' to the dictionary
            dictionary[char].append(i) 
        
        def isMatch(word):
            if word in m:
                return m[word] # return for duplicates
            l = -1
            for char in word:
                index = bisect.bisect_left(dictionary[char], l + 1)
                if index == len(dictionary[char]): # no found or dictionary[chr] is empty
                    m[word] = 0
                    return 0
                l = dictionary[char][index] # update lower bound of sub sequence
            m[word] = 1 # save the word found
            return 1
        return sum(map(isMatch, words))