Phone number to strings

Consider that a person enters a sequence of numbers on a telephone key pad. What are all the possible strings that correspond to the dialed number?

For example, consider the number 23, the possible strings are ad,ae,af,bd,be,bf,cd,ce,cf.

On a telephone keypad, there is mapping between the numbers and the letters associated. Here is the mapping. The numbers 0 and 1 are not associated with any letters.

0	0
1	1
2	a, b, c
3	d, e, f
4	g, h, I
5	j, k, l
6	m, n, o
7	p, q, r, s
8	t, u, v
9	w, x, y, z

Given a number sequence, we have to consider all possible letter combinations. We can build a recursive solution by considering one digit at a time. We stop when all the digits in the input number are explored. Here is the C++ code:

void PhoneNumbers(const string& num, const string& curr, int start) {

  const char Letters[][4] = {

    {'0'},

    {'1'},

    {'a', 'b', 'c'}, //letters starts from 2

    {'d', 'e', 'f'},

    {'g', 'h', 'i'},

    {'j', 'k', 'l'},

    {'m', 'n', 'o'},

    {'p', 'q', 'r', 's'},

    {'t', 'u', 'v'},

    {'w', 'x', 'y', 'z'}

  };

  if(start == num.length()) {

    cout << curr << endl;

    return;

  }

  int digit = num[start] - '0';

  for(int i = 0; i < 4; ++i) { //all possible letters for this digit

    char letter = Letters[digit][i];

    if (letter != 0) {

      PhoneNumbers(num,curr+letter,start+1); 

    } 

  }

}

For an input number 328, invoke the function as:

string n = "328";

PhoneNumbers(n,"",0);

The algorithm is exponential in the length of the input.

As an extension, a dictionary can be used. For an input of reasonable length, only some of the strings make valid English language words. A dictionary can be used to eliminate invalid words. A data structure, such as a hash set can be used. If the length of the input number is fixed, considering a set of dictionary words of that length is sufficient. Invalid words can also be pruned earlier in the enumeration using a dictionary stored in the form of a Trie to detect prefixes that do not occur in the dictionary.