17. 电话号码的字母组合

题目链接

DFS

class Solution {
    String[] letters = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    public List<String> letterCombinations(String digits) {
        int n = digits.length();
        List<String> ans = new ArrayList<>();
        if(n == 0) return ans;
        letterCombinations(digits, 0, new StringBuilder(), ans);
        return ans;
    }

    public void letterCombinations(String digits, int i, StringBuilder combination, List<String> ans){
        if(i == digits.length()){
            ans.add(combination.toString());
            return;
        }
        int num = digits.charAt(i) - '0';
        for(int j = 0; j < letters[num].length(); j++){
            combination.append(letters[num].charAt(j));
            letterCombinations(digits, i+1, combination, ans);
            combination.deleteCharAt(combination.length()-1);
        }
    }
}

• 先打好表，每个数字对应哪几个字母
• 然后递归dfs，枚举每个数字可能的字母，组合起来加入List中