Leetcode 17 电话号码的字母组合-Toy模板网

这篇具有很好参考价值的文章主要介绍了Leetcode 17 电话号码的字母组合。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

理解题意：

        给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合

本质上：数字代表着一个字母集合

        数字的个数决定了递归的深度，即树的深度

数字代表的字母组合决定了当前树的宽度。

        文章来源地址https://www.toymoban.com/news/detail-754896.html

1.暴力回溯

这里没有什么剪枝的约束条件，只有结束条件。

补充：StringBuilder的两个方法

StringBuilder path=new StringBuilder();
path.append(letter.charAt(i));//追加元素
path.deleteCharAt(path.length()-1);//删除末尾元素

LinkedList<String> results=new LinkedList<>();
    StringBuilder path=new StringBuilder();

    String[] letterMap=new String[]{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};


    public List<String> letterCombinations(String digits) {
        if(digits==null||digits.length()==0) return results;
        backtracking(digits,0);
        return results;
    }
    public void backtracking(String digits,int index){
        if(index==digits.length()){
            //结束条件：收集结果
            results.add(path.toString());
            return;
        }
        int digit=digits.charAt(index)-'0';
        String letter=letterMap[digit];
        for(int i=0;i<letter.length();i++){
            //遍历当前数字对应的字母集合
            //路径追加
            path.append(letter.charAt(i));
            //递归
            backtracking(digits,index+1);
            //路径回溯
            path.deleteCharAt(path.length()-1);
        }
    }

2.分析