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 = 0while pw<len(word) and ps<len(S):if word[pw]==S[ps]:pw += 1ps += 1else:ps += 1return pw==len(word)count = 0for word in words:if isSubsequence(word):count += 1return 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 = 0for c in S:for rest in waiting.pop(c,()):if len(rest)>1:waiting[rest[1]].append(rest[1:])else:count += 1return count

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

解法3：

利用一个next数组来进行预存在每个位置之后，a-z的字符第一次出现的位置，这样的做法也只需要遍历一遍S即可

class Solution:def numMatchingSubseq(self, S: str, words: List[str]) -> int:n = len(S)next_occur = [[n+1]*26 for _ in range(n+1)]for i in range(n-1,-1,-1):for j in range(26):next_occur[i][j] = next_occur[i+1][j]next_occur[i][ord(S[i])-ord('a')] = icount = 0for w in words:ind = 0point = next_occur[0][ord(w[ind])-ord('a')]while ind<len(w) and point!= n+1 and next_occur[point][ord(w[ind])-ord('a')] != n+1:point = next_occur[point][ord(w[ind])-ord('a')]+1ind += 1if ind == len(w):count += 1return count