数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Python程序：统计列表中单词串联的数量
假设我们有一个字符串列表；我们需要找到列表中哪些单词是由列表中其他单词串联而成的。在串联时可以重复使用单词，并且可以进行任意次数的串联。
例如，如果输入是words = ["hello", "world", "helloworld", "famous", "worldfamous", "programming"]，则输出为2，因为"helloworld"是"hello"和"world"的串联。"worldfamous"是"world"和"famous"的串联。
为了解决这个问题，我们将遵循以下步骤：
- trie := 一个新的映射
- 对于words中的每个单词，执行以下操作：
- layer := trie
- 对于单词中的每个字符w，执行以下操作：
- 如果layer中不存在w，则：
- layer[w] := 一个新的映射
- layer := layer[w]
- 如果layer中不存在w，则：
- layer["*"] := 一个空元组
- 定义一个函数dfs()。它将接收单词和已串联单词数作为参数。
- layer := trie
- 对于单词中的每个索引i和字符w，执行以下操作：
- 如果layer中存在"*"，则：
- 如果dfs(word[从索引i到结尾], num_concatenated_words + 1)为True，则：
- 返回True
- 如果layer中不存在w，则：
- 返回False
- 如果dfs(word[从索引i到结尾], num_concatenated_words + 1)为True，则：
- layer := layer[w]
- 如果layer中存在"*"，则：
- 如果layer中存在"*"且已串联单词数>=1，则：
- 返回True
- 返回False
- 在主方法中，执行以下操作：
- count := 0
- 对于words中的每个单词，执行以下操作：
- count := count + dfs(word, 0)
- 返回count
让我们看下面的实现来更好地理解。
示例
class Solution:
def solve(self, words):
trie = {}
for word in words:
layer = trie
for w in word:
if w not in layer:
layer[w] = {}
layer = layer[w]
layer["*"] = ()
def dfs(word, num_concatenated_words):
layer = trie
for i, w in enumerate(word):
if "*" in layer:
if dfs(word[i:], num_concatenated_words + 1):
return True
if w not in layer:
return False
layer = layer[w]
if "*" in layer and num_concatenated_words >= 1:
return True
return False
count = 0
for word in words:
count += dfs(word, 0)
return count
ob = Solution()
words = ["hello", "world", "helloworld", "famous", "worldfamous", "programming"]
print(ob.solve(words))输入
["hello", "world", "helloworld", "famous", "worldfamous", "programming"]
输出
2
更新于: 2020年11月26日
浏览量：131
广告