心之所向便是光

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

  • 2021-05-23
  • 作者 Ender
  • 2.37K 字
  • 次阅读

题目描述：

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

链接：

https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number

题目分析

  题目要求返回所有的可能情况，则我们可以使用回溯的方法，维护一个字符串，不断将数字代表的字母加入到字符串中，得到一种结果后再进行回溯，删除加入的字母，将数字代表的另一个字母加入到字符串中，这样便可以穷举所有的可能结果。而数字与字母的对应关系可以使用一个哈希表解决。注意当输入的串为空串时，也要返回一个空的字符串数组作为结果。

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
class Solution {
public:
    void Combinations(vector<string>& res, const unordered_map<char, string>& table, const string& digits, int index, string& now){
        if(index == digits.size()){
            res.push_back(now);
        }
        else{
            string letters = table.at(digits[index]);
            for(char letter : letters){
                now.push_back(letter);
                Combinations(res, table, digits, index+1, now);
                now.pop_back();
            }
        }
    }

    vector<string> letterCombinations(string digits) {
        vector<string> res;
        if(digits.empty()) return res;

        unordered_map<char, string> table {
            {'2', "abc"},
            {'3', "def"},
            {'4', "ghi"},
            {'5', "jkl"},
            {'6', "mno"},
            {'7', "pqrs"},
            {'8', "tuv"},
            {'9', "wxyz"}
        };
        string now;
        Combinations(res, table, digits, 0, now);
        return res;
    }
};

  时间复杂度：$O(3^m\times4^n)$，其中 $m$ 是输入中对应 3 个字母的数字个数，也即 2、3、4、5、6、8 数字的数量，$n$ 是输入中对应 4 个字母的数字个数，也即 7、9 数字的数量。这是因为我们需要遍历所有可能的字母组合。
  空间复杂度：$O(m+n)$，其中 $m$ 是输入中对应 3 个字母的数字个数，$n$ 是输入中对应 4 个字母的数字个数。因为返回值不计入空间复杂度中，而其他开销还有哈希表和递归调用中的层数开销。哈希表大小是固定的，可以视为常数；而最大递归层数为 $m+n$。

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
,
最后编辑：2021-06-22