程序查找python单词列表中存在的子序列数

Z时代
2024-01-10
分类：综合

假设我们有一个单词列表和一个字符串s，我们必须在单词列表中找到作为s的子序列的字符串数。

因此，如果输入像单词= [“ xz”，“ xw”，“ y”] s =“ xyz”，则输出将为2，因为“ xz”和“ y”是“ xyz”的子序列。

为了解决这个问题，我们将遵循以下步骤-

回答：= 0
d：=一个空的映射
对于单词中的每个单词，

在d [word [0]]的末尾插入单词

对于s中的每个c

如果单词的大小为1，则
除此以外，
回答：=回答+1
在d [word [1]]的末尾插入word [从索引1到末尾]的子字符串
l：= d [c]
d [c]：=一个新列表
对于l中的每个字，

返回ans

让我们看下面的实现以更好地理解-

例

from collections import defaultdict
class Solution:
   def solve(self, words, s):
      ans = 0
      d = defaultdict(list)
      for word in words:
         d[word[0]].append(word)
      for c in s:
         l = d[c]
         d[c] = []
         for word in l:
            if len(word) == 1:
               ans += 1
            else:
               d[word[1]].append(word[1:])
      return ans
ob = Solution()words = ["xz", "xw", "y"]
s = "xyz"
print(ob.solve(words, s))