17. 电话号码的字母组合（高频题）

17. 电话号码的字母组合

• 解题思路
• 代码

解题思路

一看是个组合类型的题，直接用回溯法，就可以解决，具体看注释

代码

class Solution {
    //存放最终结果
    List<String> res = new ArrayList<>();

    //存放临时结果
    StringBuffer path = new StringBuffer();

    //使用HashMap存放字符与字符串对应关系
    Map<Character, String> phoneMap = new HashMap<Character, String>() {{
        put('2', "abc");
        put('3', "def");
        put('4', "ghi");
        put('5', "jkl");
        put('6', "mno");
        put('7', "pqrs");
        put('8', "tuv");
        put('9', "wxyz");
    }};


    public List<String> letterCombinations(String digits) {
        if (digits.equals("") || digits.length() == 0) {
            return res;
        }
        //回溯
        backtraking(digits, 0);

        //返回结果
        return res;
    }

    public void backtraking(String digits, int index) {

        //终止条件："abc"遍历完成。
        if (index == digits.length()) {
            res.add(path.toString());
            return;
        }

        //获得index对应的数字
        char digit = digits.charAt(index);

        //获得数字对应的字符串
        String letter = phoneMap.get(digit);

        //遍历字符串中的字符
        for (int i = 0; i < letter.length(); i++) {
            //存入
            path.append(letter.charAt(i));

            //递归
            backtraking(digits, index + 1);

            //回溯
            path.deleteCharAt(index);
        }
    }
}