目录

• 1.问题描述
• 2.测试用例
  • 示例 1
  • 示例2
  • 示例3
• 3.提示
• 4.代码
  • 1.电话号码的字母组合-回溯
    • code
    • 复杂度

1.问题描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

2.测试用例

示例 1

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

示例2

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

示例3

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

3.提示

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

4.代码

1.电话号码的字母组合-回溯

code

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

/**
     * 回溯
     * @param digits
     * @return
     */
public List<String> letterCombinations(String digits) {
    List<String> res = new ArrayList<>();
    StringBuffer solution = new StringBuffer();
    if ("".equals(digits)) {
        return res;
    }
    dfsLetterCombination(digits, res, solution, 0);
    return res;
}

private void dfsLetterCombination(String digits, List<String> res, StringBuffer solution, int i) {
    if (i >= digits.length()) {
        res.add(solution.toString());
    } else {
        String s = digits.charAt(i) + "";
        String str = phoneMap.get(s);
        for (int j = 0; j < str.length(); j++) {
            solution.append(str.charAt(j));
            dfsLetterCombination(digits, res, solution, i + 1);
            solution.deleteCharAt(i);
        }
    }
}

复杂度

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