当前位置: 代码迷 >> 综合 >> Leetcode 792. Number of Matching Subsequences (python)
  详细解决方案

Leetcode 792. Number of Matching Subsequences (python)

热度:67   发布时间:2023-11-26 07:03:33.0

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
  相关解决方案