Given a

**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:**

`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 `String`

s. Check out the keypad and mapping below for reference.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.

2 -> "abc"

3 -> "def"

4 -> "ghi"

5 -> "jkl"

6 -> "mno"

7 -> "pqrs"

8 -> "tuv"

9 -> "wxyz"

Input : "34"

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

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

First thing's first - you need a

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 -

`HashMap`

to create and store the number - string mapping. Also, whenever you hear

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.
1) Create a

2) Use a

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

5) Return the output

`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) { }

**C**

**Java**

**Python**