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.
- 00112a, b, c3d, e, f4g, h, I5j, k, l6m, n, o7p, q, r, s8t, u, v9w, 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.
