import java.util.ArrayList;
import java.util.HashMap;
public class Solution {
private HashMap<Character,String> map;// will use map in other function so declare map here
private void setup(){
map = new HashMap<Character,String>();
map.put('1', "");
map.put('2', "abc");
map.put('3', "def");
map.put('4', "ghi");
map.put('5', "jkl");
map.put('6', "mno");
map.put('7', "pqrs");
map.put('8', "tuv");
map.put('9', "wxyz");
map.put('0', "");
}
public ArrayList<String> letterCombinations(String digits) {
setup();
ArrayList<String> solutions = new ArrayList<String>();
recursion(0,digits,solutions,new String());
return solutions;
}
private void recursion(int start, String digits,ArrayList<String> solutions,String psol){
if(psol.length() > digits.length()) return;
if(psol.length() == digits.length()) {
solutions.add(psol);
return;
}
else{
for(int i = start ; i < digits.length() ; i++){
String letter = map.get(digits.charAt(i));
for(int j = 0; j< letter.length(); j++){
recursion(i+1,digits,solutions,psol+ letter.charAt(j));// string + string = new stinrg diaobaole!
}
}
}
}
}