1-800-PROBLEM

Given a String that represents the digits pressed on a classic cell phone keypad - return all possible letter combinations that the numbers could represent in an ArrayList of Strings. Check out the keypad and mapping below for reference.

Note:
a) You can assume that the input String contains only numbers between 2 and 9.
b) The order of the combinations in the output does not matter.

Mapping:
2 -> "abc"
3 -> "def"
4 -> "ghi"
5 -> "jkl"
6 -> "mno"
7 -> "pqrs"
8 -> "tuv"
9 -> "wxyz"

Example:

Input  : "34" 
Output : [dg, dh, di, eg, eh, ei, fg, fh, fi]

Need a hand? Try out these hints, one at a time.

Quick hint to get things rolling

First thing's first - you need a HashMap to create and store the number - string mapping.

Also, whenever you hear permutations or combinations - think Depth First Search! DFS is pretty simple and follows a repeatable, predictable pattern. At Firecode.io - we love iterative Depth First traversals with a Stack, as these are easier to visualize when compared to recursive Depth First solutions. Need more help? Check out the next hint if you're stuck.

PS: Did we mention that you might want to create a local class - PhoneNode that stores the possible String up to that point in the stack, along with the number of digits remaining.

Final hint! You should be able to code the problem on viewing this.

1) Create a HashMap - mapping and store the digits to string mapping. Create a custom local class to store the required information when performing the DF traversal.

class PhoneNode{
     String word;
     int digitCount;
     PhoneNode(String w, int c){
        word = w;
        digitCount = c;
     }
 }

2) Use a Deque as a Stack - Deque stack = new LinkedList<>();

3) Push the starting 3 or 4 letter nodes onto the Stack that represents the possible letters from the first keypress

4) Perform a classic Depth first traversal. Loop in a while loop till the stack becomes empty. In each iteration, pop a PhoneNode from the stack and check if its digitCount = the length of the input digit string. If it is, add that node's word to the output ArrayList. Otherwise, create 3 or 4 new PhoneNodes that will be the children of the current PhoneNode, set their corresponding word and digitCount values and push them onto the stack.

5) Return the output ArrayList

public static  ArrayList<String> getStringsFromNums(String digits) {
      
}

This Coding Interview Question is available with an answer in the following programming languages :

Java

Python

1-800-PROBLEM

Quick hint to get things rolling

Final hint! You should be able to code the problem on viewing this.

The interview prep tool you'll fall in love with!

This Coding Interview Question is available with an answer in the following programming languages :