0017. Letter Combinations of a Phone Number ============================================ 题目信息 -------- :题号: 0017. 电话号码的字母组合 :难度: Medium :主题: 字符串、回溯、笛卡尔积 :原题: `LeetCode 0017 `_ :重点: 逐位扩展前缀、复用回溯路径、由分支数乘积确定输出规模 题目重述 -------- 给定一个只包含数字 ``2`` 到 ``9`` 的字符串 ``digits``,按照电话键盘映射返回所有可能的字母组合: ``2 -> abc``、``3 -> def``、``4 -> ghi``、``5 -> jkl``、``6 -> mno``、``7 -> pqrs``、 ``8 -> tuv``、``9 -> wxyz``。 每个数字必须选择恰好一个对应字母,组合中的字符顺序必须与数字顺序一致。若 ``digits`` 为空,返回空列表。 结果顺序不限。 自建示例 -------- * 两个三字母按键:``digits = "23"``,返回 ``["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]``; * 三字母与四字母按键:``digits = "27"``,共有 ``3 * 4 = 12`` 个组合; * 单个数字:``digits = "8"``,返回 ``["t", "u", "v"]``; * 重复数字:``digits = "22"``,两个位置独立选择,共有 ``3 * 3 = 9`` 个组合; * 空输入:``digits = ""``,返回 ``[]``。 C++ 实现 -------- .. code-block:: cpp #include #include #include class Solution { private: const std::array letters{ "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" }; std::vector iterativeProduct(const std::string& digits) { if (digits.empty()) { return {}; } std::vector result{""}; for (char digit : digits) { const std::string& choices = letters[digit - '0']; std::vector next; next.reserve(result.size() * choices.size()); for (const std::string& prefix : result) { for (char letter : choices) { next.push_back(prefix + letter); } } result.swap(next); } return result; } void backtrack(const std::string& digits, int index, std::string& path, std::vector& result) { if (index == static_cast(digits.size())) { result.push_back(path); return; } for (char letter : letters[digits[index] - '0']) { path.push_back(letter); backtrack(digits, index + 1, path, result); path.pop_back(); } } std::vector backtrackingProduct(const std::string& digits) { if (digits.empty()) { return {}; } int combinationCount = 1; for (char digit : digits) { combinationCount *= static_cast(letters[digit - '0'].size()); } std::vector result; result.reserve(combinationCount); std::string path; path.reserve(digits.size()); backtrack(digits, 0, path, result); return result; } public: std::vector letterCombinations(std::string digits) { return backtrackingProduct(digits); } }; 题解 ---- 组合结构 ~~~~~~~~ 第 ``i`` 个数字只决定答案中第 ``i`` 个字符的可选集合。例如 ``digits = "27"`` 时: * 第 0 位从 ``abc`` 中选择; * 第 1 位从 ``pqrs`` 中选择。 每个完整答案都必须从每个集合中各取一个字符,因此答案就是这些按键字母集合按输入顺序形成的笛卡尔积。 若各位置分别有 ``b0, b1, ..., bk-1`` 个选择,答案数量为: ``N = b0 * b1 * ... * bk-1``。 这意味着算法无法少于 ``N`` 次生成工作,因为这些答案本身都必须返回。 逐层扩展 ~~~~~~~~ ``iterativeProduct`` 从唯一的空前缀 ``""`` 开始。处理一个数字时,把当前每个前缀分别追加该按键的所有字母, 得到下一层前缀集合。 处理完前 ``i`` 个数字后,``result`` 恰好包含这 ``i`` 个位置的全部组合: * 初始时处理了零个位置,空前缀是唯一组合; * 假设当前已经包含前 ``i`` 位的全部组合; * 给每个前缀分别追加第 ``i`` 位的全部合法字母,就得到前 ``i + 1`` 位的全部组合,且没有重复。 这种方法直接保存每一层的全部中间字符串。结构直观,但 ``prefix + letter`` 会为每个新节点构造一个新字符串。 回溯状态 ~~~~~~~~ 回溯只需要两个核心状态: * ``index``:下一个需要选择字母的数字位置; * ``path``:前 ``index`` 个位置已经选出的前缀。 当前位置的选择集合由 ``digits[index]`` 唯一确定。不同位置可以选择相同字母,因此不需要访问标记,也不存在 “某个字母已经使用过”的限制。 每次选择一个字母后执行三步: ``追加字母 -> 递归处理下一位 -> 删除末尾字母``。 递归返回时删除刚加入的字符,``path`` 就恢复为进入本层前的父前缀。下一次循环可以复用同一个字符串缓冲区, 不会混入上一分支的选择。 叶节点 ~~~~~~ 当 ``index == digits.size()`` 时,每个数字都已经贡献一个字符,此时 ``path`` 的长度恰好等于输入长度,可以 复制到结果中。 每个合法组合对应唯一的一条逐位选择路径;回溯在每一层遍历当前按键的全部字母,所以所有路径都会到达一次。 不同组合至少在一个位置选择不同,因此不会生成重复答案。 空输入 ~~~~~~ 若直接从空前缀开始回溯,空输入会立即到达叶节点并产生 ``[""]``。题目要求的结果是空列表,因此两个入口 都先单独处理 ``digits.empty()``,把“没有数字”与“已经为所有数字完成选择”区分开。 代码演进 ~~~~~~~~ ``iterativeProduct`` 用一个结果数组保存当前整层前缀,再构造下一层数组。它把笛卡尔积的逐层展开直接写成循环。 ``backtrackingProduct`` 删除中间层数组,只保留一个可变 ``path``。内部节点只执行追加与撤销,完整字符串只在 叶节点复制。``combinationCount`` 由各按键分支数的乘积得到,用于提前预留结果容量,不参与搜索逻辑。 公开入口采用 ``backtrackingProduct``。它与组合树结构一一对应,并把除最终答案外的工作状态压缩到一条当前路径。 复杂度分析 ~~~~~~~~~~ 设数字长度为 ``k``,答案数量为 ``N``。每个答案长度为 ``k``,复制到结果需要 ``O(k)``,因此两种方法的 总时间复杂度都是 ``O(Nk)``,返回结果占 ``O(Nk)`` 空间。 迭代方法还保存当前层和下一层的中间字符串。回溯方法除返回结果外只使用长度为 ``k`` 的路径和递归栈,工作 空间为 ``O(k)``。最坏情况下每个数字有四个字母,``N = 4^k``,时间可写为 ``O(k * 4^k)``。