user2916886 - 2 months ago 8x

Python Question

I am trying to implement

`T9`

`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()

Now when I run this I should get

`[hello,hess]`

Answer

When you `map`

your `append`

function are you really meaning to map it over the *entire* `wlist`

string?

If you call `translate`

on the `wlist`

string instead of each individual letter you get:

```
hello
hess
home
abhi
busy
disturb
Words: ['hello', 'hess']
```

All you have to do is remove the `map`

call:

```
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()
```

Source (Stackoverflow)

Comments