Leetcode 17.电话号码的字母组合

题目

思路

输入的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)