17.md

17. 电话号码的字母组合

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

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

示例 1：

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

示例 2：

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

示例 3：

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

分析阶段

输入一串数字，因为每个数字在键盘上都对应一段字符串，所以相当于输入一个字符串数组。

从这个字符串数组中，遍历每个字符串，从每个字符串中取出一个字符，组成不同的组合，求解能够组成多少不同的组合。

问题变成了“在输入范围内，求解有效组合”的问题，可以使用“回溯算法”。

1、问题类型

第二类：对某种数结构和算法的使用

使用的算法：回溯算法

数据结构：回溯算法构造“空间状态树”，使用树形结构

2、解题思路

先确定键盘上数字和字符串数组的映射关系，依次遍历数字串中的每个数字，找到对应的字符串，再遍历该字符串中的字符，依次添加进“路径”中，在满足“结束条件”时，把“路径”添加进解集合中。

我们定义递归函数 $backtrack(digits, res, path, idx)$ 表示：从数字串 digits 中下标 idx 开始，确定的结果集。

接下来，依次确定“回溯算法”的必备要素，最后编码实现。

（1）选择列表

输入的数字串对应的字符串数组，作为选择列表。

（2）路径

记录字符串数组中，从每个字符串中选择的字符。

（3）结束条件

当 idx 的值等于数字串长度时，表示字符串数组中每个字符串都被遍历过，可以把路径添加进结果集。

（4）选择

因为字符串数组中，每个字符都可以被选择一次，所以在同一个 idx 值得递归中，遍历该数字对应的字符串数组，依次添加到“路径”中。

（5）空间状态树

下图中输入的数字串为：“23”。

编码阶段

class Solution {

    Map<Character, String> map = new HashMap<>(8) {
        {
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }
    };

    public static void main(String[] args) {
        String digits = "23";
        System.out.println(new Solution().letterCombinations(digits));
    }


    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return new ArrayList<>();
        }

        List<String> res = new ArrayList<>(digits.length());
        LinkedList<Character> path = new LinkedList<>();

        backtrack(digits, res, path, 0);
        return res;
    }

    private void backtrack(String digits, List<String> res, LinkedList<Character> path, int idx) {
        if (idx == digits.length()) {
            StringBuilder sb = new StringBuilder();
            for (Character character : path) {
                sb.append(character);
            }
            res.add(sb.toString());
            return;
        }

        String subString = map.get(digits.charAt(idx));
        for (int i = 0; i < subString.length(); i++) {
            path.add(subString.charAt(i));
            backtrack(digits, res, path, idx + 1);
            path.removeLast();
        }
    }
}

总结阶段

把输入的数字串转换成字符串数组，在数组中找到满足条件条件的组合，使用“回溯算法”求解。