题目来源：. - 力扣（LeetCode）
题目思路分析
题目要求我们将一个数字字符串（每个数字对应一组字母，如2对应abc，3对应def等）转换成所有可能的字母组合。这是一个典型的组合生成问题，可以使用回溯算法来解决。回溯算法通过递归地构建候选解并逐步扩展，如果某个候选解不符合要求，则“回溯”并尝试其他可能的候选解。
- 初始化映射：首先，我们需要建立一个数字到字母的映射表。
- 递归生成组合：对于输入的数字字符串，我们从第一个数字开始，依次取出其对应的字母，然后递归地处理下一个数字。
- 回溯：在递归的过程中，当处理完一个数字的所有字母后，我们需要将最后一个添加的字母从当前组合中移除（即回溯），以便尝试下一个字母。
- 终止条件：当处理完所有数字时，我们将当前组合添加到结果集中。
代码:
#include <vector>
#include <string>
#include <unordered_map> using namespace std; class Solution {
public: // 回溯函数 void Backtracking(vector<string>& ans, string digits, string& pos, int index, unordered_map<char, string> PhoneMap) { // 如果输入的数字字符串为空，直接返回 if (digits.empty()) { return; } // 当处理完所有数字时，将当前组合添加到结果集中 if (index == digits.length()) { ans.push_back(pos); return; } else { // 取出当前数字对应的字母串 char digit = digits[index++]; string letter = PhoneMap.at(digit); // 遍历当前数字的所有字母 for (char e : letter) { pos += e; // 添加字母到当前组合 Backtracking(ans, digits, pos, index, PhoneMap); // 递归处理下一个数字 pos.erase(pos.length() - 1); // 回溯，移除最后一个字母 } } } // 主函数，调用回溯函数生成所有可能的字母组合 vector<string> letterCombinations(string digits) { // 建立数字到字母的映射表 unordered_map<char, string> PhoneMap { {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"} }; vector<string> ans; // 存储所有可能的字母组合 string pos; // 当前构建的字母组合 Backtracking(ans, digits, pos, 0, PhoneMap); // 从第一个数字开始回溯 return ans; }
};注释详解
- 类定义：
Solution类包含了回溯函数Backtracking和主函数letterCombinations。 - 回溯函数：
- 参数：
ans（存储结果的向量），digits（输入的数字字符串），pos（当前构建的字母组合），index（当前处理的数字索引），PhoneMap（数字到字母的映射表）。 - 终止条件：如果
digits为空或index等于digits的长度，则结束递归。 - 递归逻辑：取出当前数字对应的字母串，遍历每个字母，添加到
pos中，然后递归处理下一个数字。递归返回后，需要移除最后一个添加的字母以尝试其他组合。
- 参数：
- 主函数：
- 初始化映射表
PhoneMap。 - 调用回溯函数
Backtracking开始生成组合。 - 返回结果集
ans。
- 初始化映射表
知识点摘要
- 回溯算法：通过递归和状态重置（回溯）来生成所有可能的解。
- 递归：函数调用自身以解决问题的一部分。
- 映射表：使用
unordered_map实现数字到字母的映射。 - 字符串操作：包括字符串的拼接和字符的移除。
通过这道题目，我们学习了如何使用回溯算法来解决组合生成问题。回溯算法是一种强大的工具，适用于解决许多涉及排列、组合和子集生成的问题。通过递归地构建候选解并逐步扩展，我们能够生成所有可能的解，并在必要时通过回溯来尝试其他解。此外，我们还学习了如何使用映射表来建立数字到字母的对应关系，以及如何进行字符串操作来构建和修改当前的组合。希望这篇文章能帮助你更好地理解和应用回溯算法。