LeetCode17.电话号码的字母组合

给定一个仅包含数字2-9的字符串返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。示例 1输入digits 23输出[ad,ae,af,bd,be,bf,cd,ce,cf]示例 2输入digits 2输出[a,b,c]解题思路看到这种组合题目脑子第一反应当然是回溯因为一个数字要对应多个字母所以我们需要先把数字和字母的关系用数组表示出来String[] letternew String[]{,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz};然后就是考虑回溯的横向和纵向显然这道题的横向就是一个数字对应的多个字母纵向就是给的digits的长度。然后就是回溯三部曲确定参数我们每一次递归都需要知道题目的digits所以可以将digits设置为一个参数还有就是有关深度的参数设置一个index来表示现在是哪一个数字。确定终止条件当我们维护的StringBuilder对象的长度和digits一样时就是终止的时刻。//终止条件 if(tmp.length()digits.length()){ result.add(new String(tmp)); return; }确定单层逻辑每一次递归深度都会增加我们需要的字符串不同所以我们必须先在数组中获取对应索引的字符串并对该字符串进行循环遍历。//先获取当前数字的字符串 String strletter[digits.charAt(index)-0]; //单层循环逻辑 for(int i0;istr.length()-1;i){ // 获取字母 tmp.append(str.charAt(i)); // 继续递归 backtracking(digits,index1); tmp.deleteCharAt(tmp.length()-1); }完整代码class Solution { StringBuilder tmpnew StringBuilder(); ListString resultnew ArrayList(); String[] letternew String[]{,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz}; public ListString letterCombinations(String digits) { // 非空判断 if(digitsnull||digits.length()0){ return result; } backtracking(digits,0); return result; } // index代表digits中数字的索引 void backtracking(String digits,int index){ //终止条件 if(tmp.length()digits.length()){ result.add(new String(tmp)); return; } //先获取当前数字的字符串 String strletter[digits.charAt(index)-0]; //单层循环逻辑 for(int i0;istr.length()-1;i){ // 获取字母 tmp.append(str.charAt(i)); // 继续递归 backtracking(digits,index1); tmp.deleteCharAt(tmp.length()-1); } } }