Java with standard backtracking (easy to understand but no great performance)


  • 1
    H
    public class Solution {
    public List<String> letterCombinations(String digits) {
        
        List<String> rst = new ArrayList<String>();
        if (digits.length() == 0) return rst;
        Map<Character, String> dict = new HashMap<Character, String>();
        dict.put('2', "abc");
        dict.put('3', "def");
        dict.put('4', "ghi");
        dict.put('5', "jkl");
        dict.put('6', "mno");
        dict.put('7', "pqrs");
        dict.put('8', "tuv");
        dict.put('9', "wxyz");
        
        char [] buffer = new char[digits.length()];
        BT(rst, digits, 0, buffer, dict);
        return rst;        
    }
    
    private void BT(List<String> rst, String digits, int index, char[] buffer, Map<Character, String> dict) {
        if (index == digits.length()) {
            StringBuffer tmp = new StringBuffer();
            for (char c : buffer) tmp.append(c);
            rst.add(tmp.toString());
            return;
        }
        
        for (int i = 0; i < dict.get(digits.charAt(index)).length(); i++) {
            buffer[index] = dict.get(digits.charAt(index)).charAt(i);
            BT(rst, digits, index + 1, buffer, dict);
        }
    }
    

    }


Log in to reply
 

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