Solution for combinatorics problem

telephone_digitis.py

# simple python script for cs106b assignment
import subprocess

words = list()

SYSTEM_DICT_LOOKUP = "egrep -i \"^%s\" /usr/share/dict/words"

class Lexicon:
    def __init__(self):
        self.word_dict = {}

    def words_for_prefix(self, prefix):
        command = SYSTEM_DICT_LOOKUP % (prefix, )
        
        try:
            result = subprocess.check_output(command, shell=True)
        except subprocess.CalledProcessError:
            return None
        
        wds = result.split("\n")
        
        if len(wds) == 0:
            return None
            
        return wds

d_to_l = { "2": "abc" , "3": "def", "4":"ghi", "5":"jkl", "6":"mno", "7":"pqrs", "8":"tuv", "9":"wxyz"}
        
def list_completions(digits, lexicon):
    if len(digits) == 1:
        # if we only have one digit, just return its possibilities
        return list(d_to_l[digits[0]])
        
    possibilities = d_to_l[digits[0]]
    
    if possibilities is None:
        return []
        
    possible_pres = list()
    
    # we find all possible suffixes of remaining part of the string
    possible_suffixes = list_completions(digits[1:], lexicon)
    
    # loop through possible first letters
    for possibility in possibilities:

        # try out possible prefixes to other possibilities
        for suffix in possible_suffixes:
            possible_pres.append(possibility + suffix)
            
    return possible_pres
        
    
english = Lexicon()
prefixes = list_completions("72547", english)

for prefix in prefixes:
    print "Looking up " + prefix + " in dictionary..."
    
    ws = english.words_for_prefix(prefix)
    
    if ws is not None:
        words.extend(ws)
        
print "Prefixes: " + ', '.join(prefixes)

print "Words: " + '\n\n-->'.join(words)