# Numbers to strings

#### Posted on March 9, 2013

##### Last updated on March 8, 2013

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.

Testing the above:

Markdown SHA1: ef1d6f926a888fb49a7a527f6e51f24dcc925081