【递归 &回溯】LeetCode-17. 电话号码的字母组合

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

给定一个仅包含数字 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'] 的一个数字。

算法分析

解题思路
DFS

• 1、先把数字和字符对应在一个哈希表中
• 2、dfs(String digits,int u,String path)：path表示当前已经有什么元素，u表示枚举到digitis的第u个字母，从哈希表中找到第u个字母对应的几个字符，分别进行枚举拼接到path后面

class Solution {

    List<String> ans = new ArrayList<>();
    String[] strs = {
        "", "", "abc", "def",
                "ghi", "jkl", "mno",
                "pqrs", "tuv", "wxyz",
    };

    public List<String> letterCombinations(String digits) {
        if (digits.isEmpty()) return new ArrayList<>();
        dfs(digits, 0, "");
        return ans;
    }

    private void dfs(String digits, int u, String path) {
        if (u == digits.length()) {
            ans.add(path);
            return;
        }
        String str = strs[digits.charAt(u) - '0'];
        for (char c : str.toCharArray()) {
            dfs(digits, u + 1, path + c);
        }
    }
}

复杂性分析

时间复杂度：O(3^m * 4^n)
空间复杂度：O(m + n)