Numbers to strings

Problem Statement:

Given an integer number \(N\), output all the possible text strings that number could make when interpreted on a standard T9 phone keyboard. For example, \(2\) maps to ["a","b","c"].

You can think of the problem as a large tree, and where each next number corresponds to a choice point between all the available letters. For example, for the input \(23\), the first node has three branches, ["a","b","c"], and each of these sub-branches has a node with another three branches, ["d","e","f"]. From this, you can see that there are \(9\) answers to this question, and in general, if every integer maps to \(3\) letters, we will have \(3^n\) combinations.

In code, we can think about this recursively. If we have only one integer \(x\), we simply return the list of all letters that \(x\) maps to in our dictionary. Otherwise, assume we have a list of integers \(L\) of length \(n\). Take the first element \(L_1\), and recursively compute all the possible combinations \(C\) of the leftover sequence \(L_2 \ldots L_n\). Then, what’s left to do is to for every combination \(c\) in \(C\), and for every letter \(l\), \(L_1\) maps to, prepend \(l\) to \(c\) and append it to our result.

The following python code demonstrates this. Notice we have to set up the dictionary first.

t9 = dict()
t9[2] = ['a','b','c']
t9[3] = ['d','e','f']
t9[4] = ['g','h','i']
t9[5] = ['j','k','l']
t9[6] = ['m','n','o']
t9[7] = ['p','q','r','s']
t9[8] = ['t','u','v']
t9[9] = ['w','x','y','z']
t9[0] = [' ']

def decode(l):
  if(len(l) == 1):
    return t9[l[0]]

  ret = []
  for d in decode(l[1:]):
    for ch in t9[l[0]]:
      ret.append(ch+d)

  return ret

Testing the above:

> print(decode([2,3,4]))
['adg', 'bdg', 'cdg', 'aeg', 'beg', 'ceg', 'afg', 'bfg', 'cfg', 'adh', 
 'bdh', 'cdh', 'aeh', 'beh', 'ceh', 'afh', 'bfh', 'cfh', 'adi', 'bdi', 
 'cdi', 'aei', 'bei', 'cei', 'afi', 'bfi', 'cfi']