跳到主要内容

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

本节目标

将递归深度绑定到数字位置，逐位选择对应按键上的字母。

这道题展示回溯决策树的另一种边界：递归第 index 层只处理输入数字串的第 index 个字符。

查看 LeetCode 原题

题意与约束​

数字 2 到 9 分别映射到三或四个小写字母。给定只含这些数字的字符串，返回每一种逐位选字母形成的组合；空字符串没有任何组合。

朴素思路与瓶颈​

可以为每一位建立多层循环，但位数不固定时循环层数也会随输入变化。递归恰好能把“处理下一位”重复表达：每层只需知道当前数字位置和已经拼好的前缀。

输入位置推进​

index 指向当前要翻译的数字，映射表给出该数字可选的字母。把一个字母加入 path 后递归处理 index + 1，返回后删除该字母。index == digits.length() 时，路径长度已经等于数字串长度，可以加入答案。

本题没有 used 或 start：每个输入位置都必须恰好使用一次，选择范围由当前位置的数字固定。空串要在开始前直接返回空列表，否则通用叶子条件会误把空路径当成一个组合。

代码实现​

C++17
#include <string>
#include <vector>

using namespace std;

class Solution {
private:
    vector<string> answer;
    string path;
    const vector<string> letters{
        "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz",
    };

    void backtrack(const string& digits, int index) {
        if (index == static_cast<int>(digits.size())) {
            answer.push_back(path);
            return;
        }

        for (char letter : letters[digits[index] - '0']) {
            path.push_back(letter);
            backtrack(digits, index + 1);
            path.pop_back();
        }
    }

public:
    vector<string> letterCombinations(string digits) {
        answer.clear();
        path.clear();
        if (digits.empty()) {
            return answer;
        }
        backtrack(digits, 0);
        return answer;
    }
};

复杂度分析​

设第 i 位数字对应 b_i 个字母，结果数为 P = ∏ b_i，数字串长度为 n。构造并复制全部字符串需要 O(n · P) 时间，递归栈和当前路径额外使用 O(n) 空间，输出空间为 O(n · P)。

易错点​

  • 把空输入返回为包含空字符串的列表，和题目要求的空列表不符。
  • 递归后没有删除刚加入的字母，后续组合会带上多余前缀。
  • 将数字字符直接当作数组下标而未转换，访问到错误映射。

模式迁移​

T9 输入、按位置替换通配符、生成固定格式的字符串和分段编码都适合此模型。只要每层决定的是“输入的下一个位置”，就用位置索引作为递归状态，而不是用 used 管理全局候选池。