我正在尝试解决此处描述的键盘自动完成问题。 问题是在给定一些字典和自动完成规则的情况下，计算一个单词需要多少次击键。例如，对于字典：
data = ['hello', 'hell', 'heaven', 'goodbye']
我们得到以下结果（请参阅上面的链接以获得进一步的解释）：
{'hell': 2, 'heaven': 2, 'hello': 3, 'goodbye': 1}
快速解释：如果用户键入h，则e自动完成，因为所有以开头的单词h也有e第二个字母。现在，如果用户输入l，另一个l被填充，给单词 2 笔画hell。当然，hello还需要再打一针。请参阅上面的链接以获取更多示例。
我的Trie代码如下，它工作正常（取自https://en.wikipedia.org/wiki/Trie）。Stack代码是从根解析树（见下面的编辑）：
class Stack(object):
def __init__(self, size):
self.data = [None]*size
self.i = 0
self.size = size
def pop(self):
if self.i == 0:
return None
item = self.data[self.i - 1]
self.i-= 1
return item
def push(self, item):
if self.i >= self.size:
return None
self.data[self.i] = item
self.i+= 1
return item
def __str__(self):
s = '# Stack contents #\n'
if self.i == 0:
return
for idx in range(self.i - 1, -1, -1):
s+= str(self.data[idx]) + '\n'
return s
class Trie(object):
def __init__(self, value, children):
self.value = value #char
self.children = children #{key, trie}
class PrefixTree(object):
def __init__(self, data):
self.root = Trie(None, {})
self.data = data
for w in data:
self.insert(w, w)
def insert(self, string, value):
node = self.root
i = 0
n = len(string)
while i < n:
if string[i] in node.children:
node = node.children[string[i]]
i = i + 1
else:
break
while i < n:
node.children[string[i]] = Trie(string[:i], {})
node = node.children[string[i]]
i = i + 1
node.value = value
def find(self, key):
node = self.root
for char in key:
if char in node.children:
node = node.children[char]
else:
return None
return node
我不知道如何计算笔画数：
data = ['hello', 'hell', 'heaven', 'goodbye']
tree = PrefixTree(data)
strokes = {w:1 for w in tree.data} #at least 1 stroke is necessary
这是从根解析树的代码：
stack = Stack(100)
stack.push((None, pf.root))
print 'Key\tChilds\tValue'
print '--'*25
strokes = {}
while stack.i > 0:
key, curr = stack.pop()
# if something:
#update strokes
print '%s\t%s\t%s' % (key, len(curr.children), curr.value)
for key, node in curr.children.items():
stack.push((key, node))
print strokes
任何想法或建设性意见都会有所帮助，谢谢！
编辑
@SergiyKolesnikov 的回答很好。为了避免调用endsWith(). 我刚刚在 Trie 类中添加了一个布尔字段：
class Trie(object):
def __init__(self, value, children, eow):
self.value = value #char
self.children = children #{key, trie}
self.eow = eow # end of word
在插入（）的末尾：
def insert(self, string, value):
#...
node.value = value
node.eow = True
然后只需替换curr.value.endswith('$'):为curr.eow. 谢谢你们！