XingHuiSamaの宝藏之地

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

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

‍

示例 1：

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

示例 2：

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

提示：

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

‍

1. 算法核心思想

这道题是经典的组合排列问题。虽然大多数标准题解都会采用深度优先搜索（DFS）的回溯算法，但我在这里采用了一种更符合人类直觉的广度优先搜索（BFS）/ 迭代“滚雪球”策略。

核心逻辑可以想象成一个不断扩建的“装配流水线”：

一开始，我们的结果篮子 result 里只有一个空字符串 [""]。
每读取到一个新的电话按键（如 '2' 对应的 a, b, c），我们就把篮子里现有的所有半成品全部拿出来。
给每一个半成品分别接上 a、b、c，组装成新的一批组合。
清空旧篮子，把这批新组合放进去。随着数字的不断读取，篮子里的组合就像滚雪球一样越滚越大，最终生成所有可能的结果。

2. 代码逻辑拆解

第一阶段：构建映射字典 (Hash Map) 利用 unordered_map 将电话按键 '2' 到 '9' 与它们对应的字母集合（vector<char>）进行精准映射，作为我们后续组装的零件库。
第二阶段：边界处理与基地初始化 （关键防坑）首先判断输入字符串 digits 是否为空，如果为空直接返回空数组 []。如果非空，则向结果集 result 中推入一个空字符串 ""，作为滚雪球的初始“内核”。
第三阶段：流水线主控 (Main Loop) 遍历输入的数字字符串 digits。针对每一个字符 c，取出它对应的字母零件盒 map[c]，然后调用组装函数 func 进行批量加工。
第四阶段：核心装配车间 (The func Helper)
- 备份与清空：首先把 result 中的当前所有组合深拷贝一份到临时仓库 mid 中，然后立刻清空 result（result.clear()），为存放新产品腾出空间。
- 笛卡尔积拼接：利用双重 for 循环。外层遍历新来的字母零件 chars[i]，内层遍历临时仓库里所有的半成品 mid[j]。将它们拼接后（mid[j] + chars[i]），重新 push_back 塞回清空后的 result 容器中。

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        // 1. 边界拦截：如果输入为空，直接返回空集（防止下面推入空字符串导致报错）
        if (digits.empty()) {
            return {};
        }

        // 2. 建立数字到字母的映射表
        unordered_map<char, vector<char>> map;
        map['2'] = {'a', 'b', 'c'};
        map['3'] = {'d', 'e', 'f'};
        map['4'] = {'g', 'h', 'i'};
        map['5'] = {'j', 'k', 'l'};
        map['6'] = {'m', 'n', 'o'};
        map['7'] = {'p', 'q', 'r', 's'};
        map['8'] = {'t', 'u', 'v'};
        map['9'] = {'w', 'x', 'y', 'z'};

        vector<string> result;
        result.push_back(""); // 放入一个空字符串，作为滚雪球的起点

        // 3. 逐个数字进行遍历处理
        for (int i = 0; i < digits.length(); i++) {
            char c = digits[i];
            func(result, map[c]);
        }
        return result;
    }

    // C++ 进阶优化：将 chars 改为 const 引用传递，避免无谓的内存拷贝
    void func(vector<string> &result, const vector<char>& chars) {
        // 将现有的半成品备份
        vector<string> mid = result; 
        // 清空原仓库，准备装新货
        result.clear(); 
        
        // 组装新产品：现有的每一个字符串 + 当前数字对应的每一个新字母
        for (int i = 0; i < chars.size(); i++) {
            for (int j = 0; j < mid.size(); j++) {
                string temp = mid[j] + chars[i];
                result.push_back(temp);
            }
        }
    }
};

3. 复杂度分析

时间复杂度：**** $\mathcal{O}(4^N \times N)$

其中 $N$ 是输入字符串 digits 的长度。键盘上每个数字最多对应 4 个字母（如 7 和 9）。在最坏情况下（例如输入全是 '7' 或 '9'），最终会生成 $4^N$ 个组合。在组装每一个组合时，字符串的拼接操作 mid[j] + chars[i] 会消耗 $\mathcal{O}(N)$ 的时间。因此整体时间复杂度为 $\mathcal{O}(4^N \times N)$ 。
空间复杂度：**** $\mathcal{O}(4^N)$

在迭代的过程中，我们使用了一个临时数组 mid 来暂存上一轮的组合结果。随着“雪球”越滚越大，mid 和 result 容器在最后一轮的最大容量都可以达到 $4^N$ 级别，因此除了最终返回的结果数组外，主要的空间开销为 $\mathcal{O}(4^N)$ 。

‍