LeetCode-17-电话号码的字母组合

17. 电话号码的字母组合

难度中等1276收藏分享切换为英文接收动态反馈

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

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

img

示例 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'] 的一个数字。

17. 1Letter Combinations of a Phone Number

Medium

5917522Add to ListShare

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

[站外图片上传中...(image-c41852-1619398504333)]

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = ""
Output: []

Example 3:

Input: digits = "2"
Output: ["a","b","c"]

Constraints:

• 0 <= digits.length <= 4
• digits[i] is a digit in the range ['2', '9'].

方法：暴力递归，深度优先遍历

image-20210426084946288

class Solution {
    public static char[][] phone = { 
            { 'a', 'b', 'c' }, // 2    0
            { 'd', 'e', 'f' }, // 3    1
            { 'g', 'h', 'i' }, // 4    2
            { 'j', 'k', 'l' }, // 5    3
            { 'm', 'n', 'o' }, // 6    
            { 'p', 'q', 'r', 's' }, // 7 
            { 't', 'u', 'v' },   // 8
            { 'w', 'x', 'y', 'z' }, // 9
    };

    // "23"
    public static List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return ans;
        }
        char[] str = digits.toCharArray();
        char[] path = new char[str.length];
        process(str, 0, path, ans);
        return ans;
    }

    // str = ['2','3']  3   3
    // str[....index-1]，按出的结果是什么都在path里
    // str[index...]  按完之后，有哪些组合，放入到ans里
    public static void process(char[] str, int index, char[] path, List<String> ans) {
        if (index == str.length) {
            ans.add(String.valueOf(path));
        } else {
            char[] cands = phone[str[index] - '2'];
            for (char cur : cands) {
                path[index] = cur;
                process(str, index + 1, path, ans);
            }
        }
    }
}

image-20210426085146937