DFS Java answer


  • 2
    M
    public List<String> letterCombinations(String digits) {
        if(digits.length()==0) return new ArrayList<String>();
        HashMap<Character, String> map = new HashMap<Character, String>();
        map.put('0',"");
        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");
        
    
        List<String> result = new ArrayList<String>();
        StringBuilder sublist = new StringBuilder();
        getCombo(digits, sublist, result, map);
        return result;
    
    }
    public void getCombo(String digits, StringBuilder sublist, List<String> result, HashMap<Character, String> map){
        if(digits.length()==0){
            //add sublist to the result
            result.add(sublist.toString());
            return;
        }
        char currDigit = digits.charAt(0);
        String possibleLetters = map.get(currDigit);
        for(int i = 0; i < possibleLetters.length(); i++){
            sublist.append( possibleLetters.charAt(i) );
            getCombo(digits.substring(1), sublist, result, map);
            sublist.replace(sublist.length() - 1, sublist.length(), "");
        }
    }

  • 0
    Z
    This post is deleted!

  • 0
    Z

    There is a bug here, in your for loop, you need to check and handle the condition of 'possibleLetters.length() == 0', i.e. when digit = 0 or 1. Call getCombo() in that case as well. Otherwise, the dfs will stop when it meets 0 or 1. Test case: "012"

    Besides, for line sublist.replace(sublist.length() - 1, sublist.length(), ""); it will be more intuitive to use the removeCharAt() method of StringBuilder.


Log in to reply
 

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