Outputting all possible words which fit a string of letters

Question

I got inspired by this C# question. It asks to write a program to output all possible words (included in a dictionary) which fit a string of letters obtained by swiping the finger over the keyboard, as is often done with mobile keyboards.

Description

Software like Swype and SwiftKey lets smartphone users enter text by dragging their finger over the on-screen keyboard, rather than tapping on each letter.

You'll be given a string of characters representing the letters the user has dragged their finger over.

For example, if the user wants "rest", the string of input characters might be "resdft" or "resert". Input

Given the following input strings, find all possible output words 5 characters or longer.

qwertyuytresdftyuioknn
gijakjthoijerjidsdfnokg

Output

Your program should find all possible words (5+ characters) that can be derived from the strings supplied.

Use http://norvig.com/ngrams/enable1.txt as your search dictionary.

The order of the output words doesn't matter.

queen question
gaeing garring gathering gating geeing gieing going goring

Notes/Hints

Assumptions about the input strings:

• QWERTY keyboard
• Lowercase a-z only, no whitespace or punctuation
• The first and last characters of the input string will always match the first and last characters of the desired output word
• Don't assume users take the most efficient path between letters
• Every letter of the output word will appear in the input string

The function read_vocabulary reads the file and saves the words in a nested dictionary structure, where the first key is the first letter of the word and the second key the last letter of the word (this improves running time by about a factor 2 with respect to a simple set).

I saved the linked word list as dictionary.txt on my computer.

The find_words function tries to find all characters of a word (with the right first and last letter) in the pattern string and yields it if it found all.

The call to sorted in the last part is not necessary from the defined interface (any ordering is fine), but I like it better this way.

All comments are welcome, especially about improving readability of the code.

import string
from collections import defaultdict


def read_vocabulary(file_name):
    vocabulary = {letter: defaultdict(set) for letter in string.lowercase}
    with open(file_name) as dict_file:
        for word in dict_file:
            word = word.strip().lower()
            vocabulary[word[0]][word[-1]].add(word)
    return vocabulary


def find_words(vocabulary, pattern, length=5):
    """
    Search `vocabulary` for words matching `pattern` generated by
    swiping the finger over the keyboard.

    Yields all matching words

    >>> vocabulary = {'q': {'n': {'queen'}, 'r': {'qualor'}}}
    >>> list(find_words(vocabulary, 'qwertyuytresdftyuioknn'))
    ['queen']
    """
    for word in vocabulary[pattern[0]][pattern[-1]]:
        if len(word) >= length:
            i = 1
            for character in word[1:-1]:
                try:
                    i = pattern.index(character, i)
                except ValueError:
                    break
            else:
                yield word

if __name__ == "__main__":
    words = ["qwertyuytresdftyuioknn",
             "gijakjthoijerjidsdfnokg",
             "cghhjkkllooiuytrrdfdftgyuiuytrfdsaazzseertyuioppoiuhgfcxxcfvghujiiuytrfddeews"]
    vocabulary = read_vocabulary("dictionary.txt")
    for word in words:
        # print word
        print " ".join(sorted(find_words(vocabulary, word), key=len, reverse=True))

Regarding run-time:

With the 1 million random characters, as linked at the other question, this code runs in about 0.14 seconds (as determined by python -m cProfile script.py), which includes reading the 1M characters from a file (because they are too big to just paste them in...).

Answer 1

Some comments:

1. You exclude words less than 5 characters when reading your vocabulary. I think it would be better to exclude them when creating the vocabulary, which reduces the number of elements in your vocabulary and avoids you needlessly looping over words that are too short.
2. Considering there are only 26 letters, it may be more efficient to have a single dictionary with two character keys rather than nested dictionaries. This would reduce the number of dictionary lookups.
3. You would need to time it to see if it helps or hurts, but one possible initial check would be to create a collections.Counter of each word in your dictionary, and a collections.Counter of pattern at the beginning, and then use the subtraction operator to make sure all the letters in each word are present in the pattern. If not, you can skip doing a linear search on that word. But the act of creating each Counter at the beginning may offset the benefit of the check.
4. Sorting will hurt your performance.

Answer 2

I would have used patterns and pattern in main instead of words and word to avoid confusion with the words of vocabulary.