17. Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

回溯，每个回溯层级添加数字对应的字符。

class Solution {
    public List<String> letterCombinations(String digits) {

        
        List<String> ret = new ArrayList<>();
        if(digits.equals("")) return ret;
        
        char[][] bin = new char[8][0];
        bin[0] = new char[]{'a', 'b', 'c'}; 
        bin[1] = new char[]{'d', 'e', 'f'};
        bin[2] = new char[]{'g', 'h', 'i'};
        bin[3] = new char[]{'j', 'k', 'l'};
        bin[4] = new char[]{'m', 'n', 'o'};
        bin[5] = new char[]{'p', 'q', 'r', 's'};
        bin[6] = new char[]{'t', 'u', 'v'};
        bin[7] = new char[]{'w', 'x', 'y', 'z'};
        
        backtracking(ret, new StringBuffer(), bin, digits, 0);
        return ret;
    }
    
    private void backtracking(List<String> ret, StringBuffer sb, char[][] bin, String digits, int i){
        if(sb.length() == digits.length() ){
            ret.add(sb.toString());
            return;
        }
        
        for(char c : bin[digits.charAt(i)-'2']){
            sb.append(c);
            backtracking(ret, sb, bin, digits, i+1);
            sb.delete(sb.length()-1, sb.length());
        }
    }
}