理解題意：

????????給定一個僅包含數字?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個字母的數字個數。

三個字母表示該層有三個分支

????????