Leetcode 792. Number of Matching Subsequences
- 题目
- 解法1:brutal force (TLE)
- 解法2:
- 解法3:
题目
解法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