Outputting all possible words which fit a string of letters 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

    &gt;&gt;&gt; vocabulary = {'q': {'n': {'queen'}, 'r': {'qualor'}}}
    &gt;&gt;&gt; list(find_words(vocabulary, 'qwertyuytresdftyuioknn'))
    ['queen']
    """
    for word in vocabulary[pattern[0]][pattern[-1]]:
        if len(word) &gt;= 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...).
I would have used patterns and pattern in main instead of words and word to avoid confusion with the words of vocabulary.