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.Input : "34"
Output : [dg, dh, di, eg, eh, ei, fg, fh, fi]
HashMap
to create and store the number - string mapping. PhoneNode
that stores the possible String
up to that point in the stack, along with the number of digits remaining.
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;
}
}
Deque
as a Stack - Deque stack
= new LinkedList<>();
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. ArrayList
public static ArrayList<String> getStringsFromNums(String digits) { }
C
Java
Python