LeetCode百题【电话号码的字母组合】

题目描述

解法

回溯，深度优先搜索
题目要求给出所有的组合结果，使用回溯，进行结果的遍历

class Solution {
    public List<String> letterCombinations(String digits) {
        //1.创建返回的结果集
        List<String> combinations=new ArrayList<>();
        //2.特殊情况处理
        if (digits.length()==0){
            return combinations;
        }
        //3.创建数字与字母的映射关系
        Map<Character,String> phoneMap=new HashMap<>();
        phoneMap.put('2', "abc");
        phoneMap.put('3', "def");
        phoneMap.put('4', "ghi");
        phoneMap.put('5', "jkl");
        phoneMap.put('6', "mno");
        phoneMap.put('7', "pqrs");
        phoneMap.put('8', "tuv");
        phoneMap.put('9', "wxyz");
        //4.调用回溯算法处理后返回结果集
        backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
        return combinations;
    }

    /**
     * 回溯
     * @param combinations 存储的结果集
     * @param phoneMap     映射关系集合
     * @param digits       输入的数字字符-> eg:"23"
     * @param index        处理数字的下标
     * @param combinBuffer 字符缓冲区，每次向其加入单个字符-> eg: a->ad->adg
     */
    public void backtrack(List<String> combinations,Map<Character,String> phoneMap,String digits,int index,StringBuffer combinBuffer){
        //1.定义递归出口
        if(index==digits.length()){
            //递归出口,一个组合完成后将其加入结果集内
            combinations.add(combinBuffer.toString());
        }
        else {
            //2.获取dights下标的字符  eg:"23"->'2'、index会因为递归而改变
            char digit=digits.charAt(index);
            //3.获取字符对应的映射关系的结果 eg:"2"->"abc"
            String letters=phoneMap.get(digit);
            int lettersCount=letters.length();
            //4.循环处理映射后的每个字符 eg:"abc"->'a','b','c'
            for (int i = 0; i < lettersCount; i++) {
                //5.用字符缓冲区存储
                combinBuffer.append(letters.charAt(i));
                //6.递归调用,与下一个下标所对应的字符组合 只改变digits的下标,最终到递归出口判断
                backtrack(combinations, phoneMap, digits, index+1, combinBuffer);
                //7.递归返回后，清除缓冲区buffer的当前字符,为下一次循环调用使用准备
                combinBuffer.deleteCharAt(index);
            }
        }
    }
}