Fast, backtracking, easy to understand, with explanations!


  • 5
    S
     public class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<String>();
        String[][] map={{},{},{"a","c","b"},{"d","e","f"},{"g","h","i"},{"j","k","l"},{"m","n","o"},{"p","q","r","s"},,{"t","u","v"},{"w","x","y","z"}};
        String single="";
        if(digits == null || digits.length() == 0){                 //corner case;
            return result;
        }
        helper(result, single, digits, map,0);                     //go into recursive
        return result;
    }
    private void helper(List<String> result, String single, String digits, String[][] map,int start){
        if (start >= digits.length()){                                     // go out condition
            result.add(single);
            return;
        }
        int index = digits.charAt(start)-'0';
        String[] current = map[index];                                  //get letter collection of current digit
        for(int i = 0; i < current.length; i++){
            single = single + current[i];                                //add one letter to current prefix
            helper(result, single, digits, map, start + 1);    //go recursive
            single=single.substring(0,single.length()-1);    //remove the last digit, prepare to change to another letter
        }
    }
    

    }


  • 0
    X

    Well done!!!!!! Good explanation


  • 1
    C

    Why do you leave the third entry of the map, from the end, empty? The map space should be contiguous.


  • 0
    F

    A few minor issues with your code: (1) as @cl0ckw0rks0 mentioned, map has an extra comma in it and (2) digits == null is equivalent to digits.length() == 0. My solution in python:

    class Solution(object):
        def letterCombinations(self, digits):
            phoneMap = [[], [], ["a","b","c"], ["d","e","f"], ["g","h","i"], ["j","k","l"], ["m","n","o"], ["p","q","r","s"], ["t","u","v"], ["w","x","y","z"]]
            result, entry, start = [], "", 0
            if not(digits): return result
            self.helper(digits, phoneMap, result, entry, start)
            return result
            
        def helper(self, digits, phoneMap, result, entry, start):
            if start == len(digits):
                return result.append(entry) 
            current = phoneMap[int(digits[start])]
            for i in xrange(len(current)):
                entry += current[i] 
                self.helper(digits, phoneMap, result, entry, start + 1)
                entry = entry[:-1] 
    

Log in to reply
 

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