Python程序：查找单词列表中存在的子序列个数

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

因此，如果输入类似于 words = ["xz", "xw", "y"] s = "xyz"，则输出将为 2，因为 "xz" 和 "y" 是 "xyz" 的子序列。

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

• ans := 0
• d := 一个空字典
• 对于words中的每个单词，执行：
  • 将单词插入到d[word[0]]的末尾
• 对于s中的每个字符c，执行：
  • l := d[c]
  • d[c] := 一个新的列表
  • 对于l中的每个单词，执行：
    • 如果单词的长度为1，则
      • ans := ans + 1
    • 否则，
      • 将单词的子字符串（从索引1到结尾）插入到d[word[1]]的末尾
• 返回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))

输入

["xz", "xw", "y"], "xyz"

输出

2

Arnab Chakraborty

更新于：2020-12-02

345 次浏览

开启您的职业生涯

完成课程获得认证

开始学习