Java backtrack solution


  • 0
    J

    Not fast but easy to understand. Similar to Combination problem.

    public class Solution {
        public List<String> letterCombinations(String digits) {
            List<String> result=new ArrayList<String>();
            if(digits==null||digits.length()==0||digits.contains("0")||digits.contains("1")){
                return result;
            }
            String[] map=new String[10];
            map[0]="";
            map[1]="";
            map[2]="abc";
            map[3]="def";
            map[4]="ghi";
            map[5]="jkl";
            map[6]="mno";
            map[7]="qprs";
            map[8]="tuv";
            map[9]="wxyz";
            StringBuilder sb=new StringBuilder();
            backtrack(sb,digits,map,result,0);
            return result;
            
        }
        
        public void backtrack(StringBuilder sb,String digits,String[] map,List<String> result,int start){
            if(sb.length()==digits.length()){
                result.add(sb.toString());
                return;
            }
            for(int i=start;i<digits.length();i++){
            	int tt=Character.getNumericValue(digits.charAt(i));
                for(int j=0;j<map[tt].length();j++){
                    sb.append(map[tt].charAt(j));
                    backtrack(sb,digits,map,result,i+1);
                    sb.deleteCharAt(sb.length()-1);
                }
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.