使用Trie查找单词列表中的复合词
问题描述:
给出一个单词列表,我想弄清楚如何在列表中找到由列表中的其他单词组成的单词。例如,如果列表是["race", "racecar", "car"]
,我想返回["racecar"]
。使用Trie查找单词列表中的复合词
这是我的一般思考过程。我知道使用一个trie可以解决这类问题。对于每个单词,我可以使用trie找到它的所有前缀(也是列表中的单词)。然后,对于每个前缀,我可以检查单词的后缀是否由单词中的一个或多个单词组成。但是,我很难实现这一点。我已经能够实现trie和和函数来获取单词的所有前缀。我只是坚持实施复合词检测。
答
如果前缀为单词,则可以将Trie节点呈现为defaultdict
已扩展为包含布尔标志标记的对象。然后,你可以有地方在第一轮添加的所有的话特里和第二轮检查每个字两遍处理,如果它是一个组合或不:
from collections import defaultdict
class Node(defaultdict):
def __init__(self):
super().__init__(Node)
self.terminal = False
class Trie():
def __init__(self, it):
self.root = Node()
for word in it:
self.add_word(word)
def __contains__(self, word):
node = self.root
for c in word:
node = node.get(c)
if node is None:
return False
return node.terminal
def add_word(self, word):
node = self.root
for c in word:
node = node[c]
node.terminal = True
def is_combination(self, word):
node = self.root
for i, c in enumerate(word):
node = node.get(c)
if not node:
break
# If prefix is a word check if suffix can be found
if node.terminal and word[i+1:] in self:
return True
return False
lst = ["race", "racecar", "car"]
t = Trie(lst)
print([w for w in lst if t.is_combination(w)])
输出:
['racecar']
+0
啊,这就是我想念的。我认为如果你稍微改变你的函数is_combination,它就会起作用。在你的条件检查后缀,我会改变它:'如果node.terminal和(自我或self.is_combination(word [i + 1:])中的单词[i + 1:])'您的代码只会查找复合词由两个词组成。但是,它们也可以由3个或更多的单词组成。非常感谢你的帮助! – user3699999
'我已经能够实现trie和和函数来获取一个单词的所有前缀“发布到目前为止您尝试过的内容。然后人们可以在你的代码上写字。 –