Wrong output in implementing T9 dictionary in python

Question

I am trying to implement T9 dictionary in python. I am using Trie to implement it. I have this code which creates a Trie from the words in the dictionary and then do a lookup for the pattern

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] as output right? But I get an empty list. What mistake am I making here?

tijko · Accepted Answer · 2016-07-23T22:18:59.737

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

thanks! I didn't noticed that map() was resulting in wrong output. — user2916886, Jul 18 '16 at 05:02

Wrong output in implementing T9 dictionary in python

1 Answers1