在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