Leetcode 17 电话号码的字母组合

理解题意：

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

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

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

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

????????

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.分析

时间复杂度：O()

空间复杂度：O(m+n)

其中m是3个字母的数字个数，n是4个字母的数字个数。

三个字母表示该层有三个分支

????????