【Check 63】2024-04-27 - 17. 电话号码的字母组合

[larscheng]

17. 电话号码的字母组合

[larscheng]

思路

回溯 哈希表记录每个数字与字符的对应关系 从字符串首位字符为起点，开始递归收集字母组合，回溯重置状态

代码

class Solution {

    public List<String> letterCombinations(String digits) {

        List<String> res = new ArrayList<>();
        if (digits.isEmpty()){
            return res;
        }
        Map<Character,char[]> map = new HashMap<>(){
            {
                put('2',new char[]{'a','b','c'});
                put('3',new char[]{'d','e','f'});
                put('4',new char[]{'g','h','i'});
                put('5',new char[]{'j','k','l'});
                put('6',new char[]{'m','n','o'});
                put('7',new char[]{'p','q','r','s'});
                put('8',new char[]{'t','u','v'});
                put('9',new char[]{'w','x','y','z'});
            }
        };
        backtrack(map,digits,res,0,new StringBuffer());
        return res;
    }

    private void backtrack(Map<Character, char[]> map, String digits, List<String> res, int index, StringBuffer temp) {
        if (index == digits.length()) {
            res.add(temp.toString());
        } else {
            for (char letter : map.get(digits.charAt(index))) {
                temp.append(letter);
                backtrack(map, digits, res, index + 1, temp);
                temp.deleteCharAt(index);
            }
        }
    }
}