String与前缀匹配

Question

我有字符串列表，这是前缀列表(假设其庞大的数字)，如果我想检查给定的名称/字符串从前缀列表最长的前缀将匹配此名称/字符串。例如前缀列表:['good'，'goo'，'go']输入:name:'goodboy'结果:good

对于列表中的少量数据，我们可以使用正常的搜索/匹配技术，但对于巨大的数据，有人能建议我如何改进吗?

Answer 1

您可以使用tree

下面是一个实现:

class Trie(dict):
def add(self, s):
node = self
for ch in s:
if ch not in node:
node[ch] = Trie() 
node = node[ch]
node["end"] = True
def findprefix(self, s):
node = self
len = 0
for i, ch in enumerate(s):
if "end" in node:
len = i
if ch not in node:
break 
node = node[ch]
return s[:len]

trie = Trie()
for s in ["good", "goo", "go", "goodbyeparty"]:
trie.add(s)
print(trie.findprefix("goodbye"))  # "good"```