• Below is my answer to the problem.
But with the test case "999" it gives a wrong answer.
I counted the number of combinations in the correct answer, it is a total of 36 combinations, which seems odd to me since 9 can represent 4 characters, leading to total combinations of 444 = 64 combinations. Is it something that I did not get correctly from the problem?

``````public class Solution {
public List<String> letterCombinations(String digits) {
HashMap<Character,ArrayList<Character>> map = new HashMap<Character,ArrayList<Character>>();
ArrayList<Character> l2 = new ArrayList<Character>(Arrays.asList('a', 'b', 'c'));
ArrayList<Character> l3 = new ArrayList<Character>(Arrays.asList('d', 'e', 'f'));
ArrayList<Character> l4 = new ArrayList<Character>(Arrays.asList('g', 'h', 'i'));
ArrayList<Character> l5 = new ArrayList<Character>(Arrays.asList('j', 'k', 'l'));
ArrayList<Character> l6 = new ArrayList<Character>(Arrays.asList('m', 'n', 'o'));
ArrayList<Character> l7 = new ArrayList<Character>(Arrays.asList('p', 'q', 'r', 's'));
ArrayList<Character> l8 = new ArrayList<Character>(Arrays.asList('t', 'u', 'v'));
ArrayList<Character> l9 = new ArrayList<Character>(Arrays.asList('w', 'x', 'y', 'z'));
map.put('2',l2);
map.put('3',l3);
map.put('4',l4);
map.put('5',l5);
map.put('6',l6);
map.put('7',l7);
map.put('8',l8);
map.put('9',l9);

List<String> result = new ArrayList<String>();
if(digits.length()==0){
return result;
}

String start = "";
fill(start,map,0,digits,result);

return result;

}

public void fill(String start, HashMap<Character,ArrayList<Character>> map, int index, String digits, List<String> result){
char c = digits.charAt(index);
if(map.get(c).size()==4){
StringBuilder sb1 = new StringBuilder(start);
StringBuilder sb2 = new StringBuilder(start);
StringBuilder sb3 = new StringBuilder(start);
StringBuilder sb4 = new StringBuilder(start);

String s1 = sb1.append(map.get(c).get(0)).toString();
String s2 = sb2.append(map.get(c).get(1)).toString();
String s3 = sb3.append(map.get(c).get(2)).toString();
String s4 = sb4.append(map.get(c).get(3)).toString();

if(index == digits.length()-1){
if(!result.contains(s1))
if(!result.contains(s2))
if(!result.contains(s3))
if(!result.contains(s4))
} else {
fill(s1,map,index+1,digits,result);
fill(s2,map,index+1,digits,result);
fill(s4,map,index+1,digits,result);
}
} else {
StringBuilder sb1 = new StringBuilder(start);
StringBuilder sb2 = new StringBuilder(start);
StringBuilder sb3 = new StringBuilder(start);

String s1 = sb1.append(map.get(c).get(0)).toString();
String s2 = sb2.append(map.get(c).get(1)).toString();
String s3 = sb3.append(map.get(c).get(2)).toString();

if(index == digits.length()-1){
if(!result.contains(s1))
if(!result.contains(s2))
if(!result.contains(s3))

} else {
fill(s1,map,index+1,digits,result);
fill(s2,map,index+1,digits,result);
fill(s3,map,index+1,digits,result);

}
}
}
}``````