Vault 101

xjay2007's Blog

0%

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

发表于 更新于 分类于 ， Valine：

题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

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

img

示例:

1
2
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

题解

回溯算法

遍历每个数字所有的可能性，如果进行到最后一个数字，则将结果放入数组中。

复杂度

  • 时间复杂度：，N 为对应有 3 个字符的数字（例如：2, 3, 4, 5, 6, 8）的个数，M 为对应有 4 个字符的数字（例如：7, 9）的个数，N+M 为输入的所有数字数目。
  • 空间复杂度：，因为结果有 种。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// C++
vector<string> letterCombinations(string digits) {
    vector<string> ret;
    if (digits.length() == 0) {
        return ret;
    }
    backtrack(digits, 0, "", ret);
    return ret;
}
void backtrack(string& digits, int level, string s, vector<string>& ret) {
    if (level == digits.length()) {
        ret.push_back(s);
        return;
    }
    auto charString = getCharString(digits[level] - '0');
    for (auto ch : charString) {
        backtrack(digits, level + 1, s + ch, ret);
    }
}
string getCharString(int n) {
    if (n < 2 || n > 9) {
        return "*";
    }
    int idx = n - 2;
    vector<string> map = {
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz",
    };
    return map[idx];
}

参考链接

相似文章