17. 电话号码的字母组合

难度：🟡 Medium | 标签：回溯、字符串 | 状态：⬜ LeetCode 链接

思路

按数字逐层 DFS，每层枚举当前数字对应的字母。

代码

class Solution {
    static constexpr const char* map_[] = {
        "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
    };
    vector<string> res;
    string path;
    void dfs(const string& d, int i) {
        if (i == (int)d.size()) { res.push_back(path); return; }
        for (char c : string(map_[d[i] - '0'])) {
            path.push_back(c);
            dfs(d, i + 1);
            path.pop_back();
        }
    }
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        dfs(digits, 0);
        return res;
    }
};

复杂度

• 时间 O(4ⁿ · n)，空间 O(n)

易错 / 回顾

• 空字符串返回 {} 不是 {""}
• 7 和 9 是 4 个字母（pqrs、wxyz）
• BFS 队列法也行，但回溯更紧凑