ここで説明されているキーボードのオートコンプリートの問題を解決しようとしています。 問題は、いくつかの辞書とオートコンプリートのルールが与えられた場合に、単語に必要なキーストロークの数を計算することです。たとえば、辞書の場合:
data = ['hello', 'hell', 'heaven', 'goodbye']
次の結果が得られます (詳細については、上記のリンクを参照してください)。
{'hell': 2, 'heaven': 2, 'hello': 3, 'goodbye': 1}
簡単な説明: ユーザーがを入力するhと、eで始まるすべての単語は2 番目の文字hも持つため、オートコンプリートされます。eユーザーが を入力するlと、もう一方lが塗りつぶされ、 という単語が 2 ストロークになりますhell。もちろん、helloもう 1 ストローク必要です。その他の例については、上記のリンクを参照してください。
私の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によるすばらしい答え。への呼び出しを避けるためにできる小さな変更が 1 つあります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
そして、insert() の最後に:
def insert(self, string, value):
#...
node.value = value
node.eow = True
curr.value.endswith('$'):次に、に置き換えるだけcurr.eowです。皆さん、ありがとうございました！