题目
思路
输入的digits有几个数就有几层。
一层中有几个数则取决于输入的数字对应的字母有几个。
1.确定递归函数的返回值及参数:
其实参数不是一开始就确定好的,而是你在写递归函数的时候缺啥,就往进去传啥。
这里我就直接全部写出来。
首先也是设定两个全局变量。一个是path存放符合条件单一结果。如:“ad”。一个是result,是所有path的集合[“ad”,“ae”…]。
然后是局部变量,一个是要输入的digits,一个是numString(它是数字和字母的映射表),一个是index(用来确定要处理digits中的哪个数字)
2.回溯函数终止条件
当path.len==digits.len时终止。
3.单层搜索的过程
用path保存当前数字对应的字母
递归搜索当前节点的所有子节点
回溯,remove
细节:怎样实现字母和数字的映射呢?很直接的一个想法哈希表。我们这里用数组哈希。
String[] numString = {“”, “”, “abc”, “def”, “ghi”, “jkl”, “mno”, “pqrs”, “tuv”, “wxyz”};
用数组的index当作key。
代码
import java.util.ArrayList;
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
List<String> res = new ArrayList<>();
StringBuffer path = new StringBuffer();
public List<String> letterCombinations(String digits) {
if (digits.length() == 0) {
return res;
}
String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
backTracking(digits, numString, 0);
return res;
}
public void backTracking(String digitis, String[] numString, int index) {
if (path.length() == digitis.length()) {
res.add(path.toString());
return;
}
//获取当前访问的数字对应的字母组
String str = numString[digitis.charAt(index) - '0'];
for (int i = 0; i < str.length(); i++) {
path.append(str.charAt(i));
backTracking(digitis, numString, index + 1);
path.deleteCharAt(path.length() - 1);
}
}
}
//leetcode submit region end(Prohibit modification and deletion)