回溯算法 17. 电话号码的字母组合

Mashiro

2022 年 12 月 20 日

399 次浏览

暂无评论

416字数

算法

# 回溯算法   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'] 的一个数字。
```

代码

```java
public static List<String> letterCombinations(String digits) {
    if ("".equals(digits)) {
        return new ArrayList<>(0);
    }
    List<String> rsList = new ArrayList<>((int) Math.pow(3, digits.length()));
    Map<Character, List<Character>> map = Map.of(
            '2', List.of('a', 'b', 'c'), '3', List.of('d', 'e', 'f'),
            '4', List.of('g', 'h', 'i'), '5', List.of('j', 'k', 'l'),
            '6', List.of('m', 'n', 'o'), '7', List.of('p', 'q', 'r', 's'),
            '8', List.of('t', 'u', 'v'), '9', List.of('w', 'x', 'y', 'z')
    );
//        例：digits = "2"
    generateString(digits, 0, rsList, map, new StringBuilder());
    return rsList;
}

private static void generateString(String str, int p, List<String> list, Map<Character, List<Character>> map, StringBuilder sb) {
    if (p == str.length()) {
        list.add(sb.toString());
        return;
    }
//        'a', 'b', 'c'
    for (Character ch : map.get(str.charAt(p))) {
//            1. a
//            2. b
//            3. c
        sb.append(ch);
//            递归进入 p == 1   str.len == 1
//            toString加入集合后返回
        generateString(str, p + 1, list, map, sb);
//            1. 删除a
//            2. 删除b
//            3. 删除c
        sb.deleteCharAt(p);
    }
}
```

最后修改：2022 年 12 月 20 日