使用 Trie 查找单词列表中的复合词
Find Compound Words in List of Words using Trie
给定一个单词列表,我想弄清楚如何在该列表中查找由列表中的其他单词组成的单词。例如,如果列表是 ["race", "racecar", "car"]
,我想 return ["racecar"]
。
这是我的大致思路。我知道使用 trie 对这类问题有好处。对于每个单词,我可以使用 trie 查找它的所有前缀(也是列表中的单词)。然后对于每个前缀,我可以检查单词的后缀是否由 trie 中的一个或多个单词组成。但是,我很难实现这一点。我已经能够实现 trie 和函数来获取单词的所有前缀。我只是坚持实施复合词检测。
您可以将 Trie 节点呈现为 defaultdict
对象,这些对象已扩展为包含布尔标志标记,如果前缀是单词。然后你可以进行两次处理,第一轮将所有单词添加到 Trie 中,第二轮检查每个单词是否为组合:
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']
给定一个单词列表,我想弄清楚如何在该列表中查找由列表中的其他单词组成的单词。例如,如果列表是 ["race", "racecar", "car"]
,我想 return ["racecar"]
。
这是我的大致思路。我知道使用 trie 对这类问题有好处。对于每个单词,我可以使用 trie 查找它的所有前缀(也是列表中的单词)。然后对于每个前缀,我可以检查单词的后缀是否由 trie 中的一个或多个单词组成。但是,我很难实现这一点。我已经能够实现 trie 和函数来获取单词的所有前缀。我只是坚持实施复合词检测。
您可以将 Trie 节点呈现为 defaultdict
对象,这些对象已扩展为包含布尔标志标记,如果前缀是单词。然后你可以进行两次处理,第一轮将所有单词添加到 Trie 中,第二轮检查每个单词是否为组合:
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']