题目描述

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

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

样例

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

说明

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

算法

(递归) $O(4^l)$

1. 可以通过手工或者循环的方式预处理每个数字可以代表哪些字母。
2. 通过递归尝试拼接一个新字母。
3. 递归到目标长度，将当前字母串加入到答案中。
4. 注意，有可能数字串是空串，需要特判。

时间复杂度

• 由于使用了递归的方式，时间复杂度与答案个数相同。
• 设数字串长度为 $l$，则最坏时间复杂度为 $O(4^l)$。

C++ 代码

class Solution {
public:
    vector<char> digit[10];
    vector<string> res;

    void init() {
        char cur = 'a';
        for (int i = 2; i < 10; i++) {
            for (int j = 0; j < 3; j++)
                digit[i].push_back(cur++);
            if (i == 7 || i == 9)
                digit[i].push_back(cur++);
        }
    }

    void solve(string digits, int d, string cur) {
        if (d == digits.length()) {
            res.push_back(cur);
            return;
        }

        int cur_num = digits[d] - '0';

        for (int i = 0; i < digit[cur_num].size(); i++)
            solve(digits, d + 1, cur + digit[cur_num][i]);
    }

    vector<string> letterCombinations(string digits) {
        if (digits == "")
            return res;
        init();
        solve(digits, 0, "");
        return res;
    }
};