假设我们有一个字符串列表;我们还必须在列表中找到与其他单词串联的单词数量。连接和连接任意次数时,我们可以重用单词。
因此,如果输入像单词= [“” hello“,” world“,” helloworld“,” famous“,” worldfamous“,” programming“]]一样,则输出将为2,因为“ helloworld”是“hello”和“world”。“worldfamous”是“world”和“famous”的串联。
让我们看下面的实现以更好地理解:
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