day152—回溯—电话号码的字母组合（LeetCode-17）
题目描述
给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23"输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = "2"输出：["a","b","c"]
提示：
1 <= digits.length <= 4digits[i]是范围['2', '9']的一个数字。
解决方案：
这段代码的核心功能是生成电话号码数字串对应的所有字母组合（比如输入 "23" 输出 ["ad","ae","af","bd","be","bf","cd","ce","cf"]），采用「类成员变量 + 递归回溯」的传统写法实现，替代了原 lambda 表达式的递归方式，时间复杂度O(3^m × 4^n)（m是对应 3 个字母的数字个数，n是对应 4 个字母的数字个数），空间复杂度O(len)（len为数字串长度，递归栈 + 路径字符串开销），是该问题的经典回溯解法。
核心逻辑（总体）
代码通过类成员变量共享递归所需的核心数据，再通过深度优先搜索（DFS）的回溯思想，逐位遍历数字对应的字母，拼接出所有可能的组合：
- 类成员变量设计：
MAPPING：固定的数字→字母映射表，对应电话键盘的数字 - 字母关系；ans：存储最终所有字母组合的结果数组；path：临时存储当前拼接的字母路径（比如处理到第 2 位时，path 可能是 "a"）；digits/len：存储输入的数字串和其长度，供递归函数访问；
- 递归辅助函数
dfs：- 参数
i：表示当前处理到数字串的第i位； - 终止条件：
i == len时，说明所有数字都处理完毕，将当前路径path加入结果数组ans； - 核心逻辑：取出第
i位数字对应的字母集，遍历每个字母并填入path[i]，递归处理下一位数字（i+1），完成回溯遍历；
- 参数
- 主函数
letterCombinations：- 边界处理：输入数字串为空时直接返回空数组；
- 初始化成员变量：将输入的数字串、长度、路径字符串（初始化长度为数字串长度）赋值给类成员；
- 启动递归：调用
dfs(0)从第 0 位数字开始处理，最终返回结果数组ans。
总结
- 核心思路：用回溯法遍历所有可能的字母组合，逐位确定数字对应的字母，递归到底时保存完整组合；
- 关键设计：将递归所需的结果、路径、输入等数据设为类成员变量，避免递归函数传递大量参数，简化逻辑；
函数源码：
#include <vector> #include <string> using namespace std; class Solution { public: // 数字到字母的映射表（类内私有常量） const string MAPPING[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; // 结果数组（类内私有成员，供辅助函数访问） vector<string> ans={}; // 临时存储当前路径的字符串 string path=""; // 输入的数字字符串 string digits=""; // 数字字符串的长度 int len=digits.length(); // 递归辅助函数 void dfs(int i) { // 递归终止条件：遍历完所有数字 if (i == len) { ans.emplace_back(path); return; } // 获取当前数字对应的字母集 string letters = MAPPING[digits[i] - '0']; // 遍历当前数字的所有可能字母 for (auto c : letters) { path[i] = c; // 记录当前位置的字母 dfs(i + 1); // 递归处理下一个数字 } } vector<string> letterCombinations(string digits) { this->len = digits.length(); // 边界条件：空字符串直接返回空数组 if (this->len == 0) { return {}; } // 初始化成员变量 this->digits = digits; this->path = string(this->len, 0); // 初始化路径字符串长度为数字长度 // 调用递归辅助函数，从第0个数字开始处理 dfs(0); return this->ans; } };