Leetcode 792. Number of Matching Subsequences (python)

题目

解法1：brutal force (TLE)

用双指针法判断某个word是不是S的subsequence。

class Solution:
    def numMatchingSubseq(self, S: str, words: List[str]) -> int:
        def isSubsequence(word):
            pw = ps = 0
            while pw<len(word) and ps<len(S):
                if word[pw]==S[ps]:
                    pw += 1
                    ps += 1
                else:
                    ps += 1
            
            return pw==len(word)
        
        count = 0
        for word in words:
            if isSubsequence(word):
                count += 1
        
        return count

解法2：

将word以第一个首字母进行分组，储存在字典中，然后不断更新字典，例子如下：

class Solution:
    def numMatchingSubseq(self, S: str, words: List[str]) -> int:
        waiting = collections.defaultdict(list)
        
        for word in words:
            waiting[word[0]].append(word[:])
        
        count = 0
        for c in S:
            for rest in waiting.pop(c,()):
                if len(rest)>1:
                    waiting[rest[1]].append(rest[1:])
                else:
                    count += 1
        return count

这种解法只需要遍历所有word和一遍S即可