T9
.NET에서 사전 을 구현하려고합니다 python
. 나는 Trie
그것을 구현하는 데 사용 하고 있습니다. Trie
사전에있는 단어에서 를 생성 한 다음 패턴을 찾는 이 코드가 있습니다.
import string
PHONE_LETTERS = 'abcdefghijklmnopqrstuvwxyz'
PHONE_NUMBERS = '22233344455566677778889999'
PHONE_TRANS = string.maketrans(PHONE_LETTERS, PHONE_NUMBERS)
class Node:
def __init__(self, key):
self.children = {}
self.key = key
self.values = []
def append_word(node, sequence, completeword):
if not sequence:
return
key = sequence[0]
try:
child = node.children[key]
except KeyError:
child = Node(key)
node.children[key] = child
if len(sequence) == 1:
child.values.append(completeword)
else:
append_word(child, sequence[1:], completeword)
def lookup(node, sequence=None):
if sequence:
# there are still numbers in the sequence: follow them in the trie
try:
child = node.children[sequence[0]]
return lookup(child, sequence[1:])
except KeyError:
return []
else:
# the sequence is empty: explore the trie using a DFS
result = node.values[:]
for child in node.children.values():
result.extend(lookup(child))
return result
def main():
root = Node(None)
words = ['hello','hess','home','abhi','busy','disturb']
for wlist in words:
print wlist
map(lambda l: append_word(root, l.strip().translate(PHONE_TRANS), l.strip()), wlist)
words = sorted(lookup(root, '43'))
print "Words: %s" % words
if __name__ == '__main__':
main()
이제 이것을 실행하면 [hello,hess]
출력이 올바르게 표시됩니까? 그러나 나는 빈 목록을 얻습니다. 내가 여기서 어떤 실수를하고 있는가?
때 map
당신의 append
기능은 정말 이상 매핑하는 것을 의미하는 전체 wlist
문자열?
당신이 전화를하면 translate
온 wlist
대신에 당신이 얻을 각 개별 문자의 문자열 :
hello
hess
home
abhi
busy
disturb
Words: ['hello', 'hess']
map
통화를 제거하기 만하면됩니다.
import string
PHONE_LETTERS = 'abcdefghijklmnopqrstuvwxyz'
PHONE_NUMBERS = '22233344455566677778889999'
PHONE_TRANS = string.maketrans(PHONE_LETTERS, PHONE_NUMBERS)
class Node:
def __init__(self, key):
self.children = {}
self.key = key
self.values = []
def append_word(node, sequence, completeword):
if not sequence:
return
key = sequence[0]
try:
child = node.children[key]
except KeyError:
child = Node(key)
node.children[key] = child
if len(sequence) == 1:
child.values.append(completeword)
else:
append_word(child, sequence[1:], completeword)
def lookup(node, sequence=None):
if sequence:
# there are still numbers in the sequence: follow them in the trie
try:
child = node.children[sequence[0]]
return lookup(child, sequence[1:])
except KeyError:
return []
else:
# the sequence is empty: explore the trie using a DFS
result = node.values[:]
for child in node.children.values():
result.extend(lookup(child))
return result
def main():
root = Node(None)
words = ['hello','hess','home','abhi','busy','disturb']
for wlist in words:
print wlist
# XXX here, you shouldn't be mapping the `translate` call onto the entire string
append_word(root, wlist.strip().translate(PHONE_TRANS), wlist)
words = sorted(lookup(root, '43'))
print "Words: %s" % words
if __name__ == '__main__':
main()
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다