在Python中查找单词列表中存在于子序列中的子序列的程序

在Python中查找单词列表中存在于子序列中的子序列的程序

假设我们有一个单词列表和一个字符串s,我们需要找出单词列表中是s的子序列的字符串数量。

所以,如果输入为words = [“xz”, “xw”, “y”],s = “xyz”,那么输出将为2,因为”xz”和”y”是”xyz”的子序列。

为了解决这个问题,我们将按以下步骤进行 –

  • 答案:= 0
  • d:=一个空映射
  • 对于单词中的每个单词,做一下
    • 在d [word [0]]的末尾插入单词
  • 对于s中的每个c,做一下
    • l:= d [c]
    • d [c]:=一个新列表
    • 对于l中的每个单词,做一下
      • 如果单词的大小为1,则
      • ans:=ans+1
      • 否则,
      • 在d [word [1]]的末尾插入单词[from index 1 to end]的子字符串
  • 返回ans

让我们看下面的实现,以便更好地理解 –

更多Python相关文章,请阅读:Python 教程

例子

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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程