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

假设我们有一个单词列表和一个字符串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))

    输入值

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

    输出结果

    2
    猜你喜欢