Classic interview question :
Print all possible words from phone number digits.
This question is asked by companies like microsoft, google, facebook. Lets see example input/output to understand this problem.
This is the cellphone keypad
Where pressing ‘2’ you can type letters -> ‘a’,’b’,’c’
using 3 -> ‘d’,’e’,’f’ etc.
So given the number 23 what are the possible words ??
ad,ae,af
bd,be,bf
ce,ce,cf
To make it clear in your head you can imagine, what happens when you press 2,3 keys while typing a text, if you press 2 first and then 3 what different words can you type ? (Answer is list of words written above) since you pressed two keys all the words will be of length 2.
Lets write a function that given the key as input returns list of characters it represents, so for instance if key is ‘2’ function returns a char[] {‘a’,’b’,’c’}.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
private char[] GetCharacters(char x) { //You should perform validation for x here. char[] arr; switch (x) { case '0': arr = new char[1] { '0' }; return arr; case '1': arr = new char[1] { '1' }; return arr; case '2': arr = new char[3] { 'a', 'b', 'c' }; return arr; case '3': arr = new char[3] { 'd', 'e', 'f' }; return arr; case '4': arr = new char[3] { 'g', 'h', 'i' }; return arr; case '5': arr = new char[3] { 'j', 'k', 'l' }; return arr; case '6': arr = new char[3] { 'm', 'n', 'o' }; return arr; case '7': arr = new char[4] { 'p', 'q', 'r', 's' }; return arr; case '8': arr = new char[3] { 't', 'u', 'v' }; return arr; case '9': arr = new char[4] { 'w', 'x', 'y', 'z' }; return arr; default: return null; } } |
Now lets write a recursive function that will use the above function to print all possible words.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
private List<string> strs = new List<string>(); private int depth = 0; char[] numbersArray; private void PrintLetters(string numbers) { this.numbersArray = numbers.ToCharArray(); this.PrintAllCombinations(this.GetCharacters(this.numbersArray[0]), string.Empty); } private void PrintAllCombinations(char[] letters, string output) { depth++; for (int i = 0; i < letters.Length; i++) { if (this.depth != 3) { output += letters[i]; this.PrintAllCombinations(this.GetCharacters(Convert.ToChar(this.numbersArray[depth])), output); } else { this.strs.Add(output + letters[i]); } } } |
I am using a variable depth, to stop the recursion. And using Console.Writeline() to print the strings.
Interesting application of this problem can be, to convert given phone number to a readable word.
for example : 27753 -> APPLE.
Leave a comment if you like the post. 🙂