电话号码的字母组合

GitHub跳转原题关系图返回列表

回溯枚举每个数字对应的字母选择，递归层数对应数字位置，每层分支数由按键映射决定。

OJ: leetcodecn

题目 ID: letter-combinations-of-a-phone-number

难度:普及/提高-

标签:回溯枚举递归

日期: 2026-07-29 11:15

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

给定仅含数字 2-9 的字符串 digits，每个数字对应一组字母（如 2→abc、7→pqrs、9→wxyz），返回所有可能的字母组合。空输入返回空列表。

思路

每层递归处理一个数字，枚举该数字映射的所有字母，选一个后递归到下一层。这棵递归树的深度等于 digits 的长度，每层分支数由对应按键决定（7 和 9 各 4 个字母，其余 3 个）。

先看一个可以直接验证想法的朴素解：

cpp
// brute.cpp：小数据暴力解，枚举每个数字对应的所有字母选择。
#include <bits/stdc++.h>
using namespace std;

const string m[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

int n;
string digits;
string cur;
vector<string> ans;

void dfs(int i) {
    if (i == n) {
        ans.push_back(cur);
        return;
    }
    for (char ch : m[digits[i] - '0']) {
        cur.push_back(ch);
        dfs(i + 1);
        cur.pop_back();
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> digits;
    n = digits.size();
    if (n == 0)
        return 0;
    dfs(0);
    for (auto &s : ans)
        cout << s << ' ';
    return 0;
}

朴素解与最终做法完全相同——本题的回溯枚举本身就是最优方案，因为必须输出所有组合，总方案数 4k4^k 无法省略。brute.cpp 与 main.cpp 的区别仅在代码组织形式。

关键实现：cur 在递归前 push_back，递归后 pop_back，保证每个位置的选择、递归、恢复三步对称；dfs(i) 表示正在决定第 i 位数字对应的字母。

空输入直接返回空列表，不需要进入递归。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty())
            return {};
        vector<string> m = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        vector<string> ans;
        string cur;
        function<void(int)> dfs = [&](int i) {
            if (i == (int)digits.size()) {
                ans.push_back(cur);
                return;
            }
            for (char ch : m[digits[i] - '0']) {
                cur.push_back(ch);
                dfs(i + 1);
                cur.pop_back();
            }
        };
        dfs(0);
        return ans;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    for (auto &x : Solution().letterCombinations(s))
        cout << x << ' ';
    return 0;
}
python
#!/usr/bin/env python3
from typing import List


class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        mp = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
        ans, cur = [], []

        def dfs(i):
            if i == len(digits):
                ans.append("".join(cur))
                return
            for ch in mp[int(digits[i])]:
                cur.append(ch)
                dfs(i + 1)
                cur.pop()

        dfs(0)
        return ans


def main():
    s = input().strip()
    print(*Solution().letterCombinations(s))


if __name__ == "__main__":
    main()

复杂度

  • 时间复杂度：O(4k⋅k)O(4^k \cdot k)，其中 k=len(digits)k = \text{len(digits)}。每个组合需要 kk 步构建，总组合数最多 4k4^k（每个数字最多 4 个字母）。
  • 空间复杂度：O(k)O(k)，递归栈深度为 kk。

总结

本题是典型的回溯枚举：递归树的每一层对应一个决策点（选择哪个字母），所有合法路径的终点就是答案。关键是理解 选择 → 递归 → 撤销 的三步对称结构。