代码随想录 Q71电话号码的字母组合

思路：

1.数字和字母如何映射？

答：可以使用map或者定义一个二维数组来做映射。如：

//初始对应所有的数字，为了直接对应2-9，新增了两个无效的字符串"" String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

2.如何解决n个for循环的问题？

答：回溯法。例如输入“2，3”，抽象为树形结构，如下图所示。

图中可以看出遍历的深度就是输入集合的长度，而叶子节点就是想要收集的结果。

回溯三部曲：

1.确定回溯函数的参数：

（1）全局变量：需要一个字符串s收集叶子节点的结果，需要一个字符串数组result保存结果。

//设置全局列表存储最后的结果 List<String> list = new ArrayList<>();

（2）参数：题目给的字符串 String digits，初始化所有数字对应字符的numString，和int型的index（和之前组合中记录下一次遍历的起始位置的startIndex不同，index用于记录遍历到第几个数字了，用来遍历digits，同时index也表示树的深度）。

public void backTracking(String digits, String[] numString, int index)

2.确定终止条件：如果index == 输入数字的个数，就收集结果，结束本层递归。

//终止条件，如果到达最后一个元素则将当前的这个结果放入list结果集 if (index == digits.length()) { list.add(temp.toString()); return; }

3.确定单层搜索的过程：首先要取index指向的数字，并找到对应的字符集（收集键盘的字符集），然后用for循环来处理这个字符集。注意此处for不从index或者startIndex开始遍历，而是从1开始，这是因为本题中每一个数字代表的是不同的集合，相当于求不同集合之间的组合，而之前的组合问题相当于求同一个集合中的组合。

//str表示当前index对应的字符串 String str = numString[digits.charAt(index) - '0']; for(int i = 0;i<str.length();i++){ temp.append(str.charAt(i)); //递归，处理下一层 backTracking(digits,numString,index + 1); //剔除末尾的继续尝试 temp.deleteCharAt(temp.length() - 1); }

附代码：

class Solution { List<String> list = new ArrayList<>(); //每次迭代都会获取一个字符串，涉及大量字符串的拼接，选择更高效的StringBuilder StringBuilder temp = new StringBuilder(); public List<String> letterCombinations(String digits) { if(digits == null || digits.length() == 0){ return list; } //初始化所有数字对应的字母，为了直接对应2-9，新增了两个无效的字符串“ ” String[] numString = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; backTracking(digits,numString,0); return list; } private void backTracking(String digits,String[] numString,int index){ if(index == digits.length()){ //遍历完全部元素后，一次性记录得到的字符串 list.add(temp.toString()); return; } //str表示当前index对应的字符串 String str = numString[digits.charAt(index) - '0']; for(int i = 0;i<str.length();i++){ temp.append(str.charAt(i)); // 递归，处理下一层 backTracking(digits,numString,index + 1); // 剔除末尾的继续尝试 // deleteCharAt表示删掉指定位置的字符（不能deleteCharAt(str.charAt(i))） temp.deleteCharAt(temp.length() - 1); } } }