【LeetCode】17、电话号码的字母组合

17. 电话号码的字母组合

题外话：

今天继续刷LeetCode，发现一不小心入选了，《数据结构与算法领域内容榜》，全靠各位大佬们的支持，感谢感谢。

接下来，继续刷题，解析，希望能对想学习算法的同学，有所帮助。

题目：

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

提示：

0 <= digits.length <= 4
digits[i] 是范围 [‘2’, ‘9’] 的一个数字。

解题思路：

此题难度简单，首先，看到所有组合，大家的第一反应估计就是回溯，是的，没错，这题完全可以用回溯来解题。

可以先用一个map，来存储所有的数字对应的字母。。

使用回溯法，一一穷举，列尽所有可能解即可。

参考代码：

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

    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;

    }

    //每次迭代获取一个字符串，所以会设计大量的字符串拼接，所以这里选择更为高效的 StringBuild
    StringBuilder temp = new StringBuilder();

    //比如digits如果为"23",num 为0，则str表示2对应的 abc
    public void backTracking(String digits, String[] numString, int num) {
    
        //遍历全部一次记录一次得到的字符串
        if (num == digits.length()) {
    
            list.add(temp.toString());
            return;
        }
        //str 表示当前num对应的字符串
        String str = numString[digits.charAt(num) - '0'];
        for (int i = 0; i < str.length(); i++) {
    
            temp.append(str.charAt(i));
            //c
            backTracking(digits, numString, num + 1);
            //剔除末尾的继续尝试
            temp.deleteCharAt(temp.length() - 1);
        }
    }
}