当前位置：首页 > news >正文

C++算法练习-day53——17.电话号码的字母组合

news 来源：原创 2025/5/12 3:16:09

题目来源：. - 力扣（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实现数字到字母的映射。
字符串操作：包括字符串的拼接和字符的移除。

通过这道题目，我们学习了如何使用回溯算法来解决组合生成问题。回溯算法是一种强大的工具，适用于解决许多涉及排列、组合和子集生成的问题。通过递归地构建候选解并逐步扩展，我们能够生成所有可能的解，并在必要时通过回溯来尝试其他解。此外，我们还学习了如何使用映射表来建立数字到字母的对应关系，以及如何进行字符串操作来构建和修改当前的组合。希望这篇文章能帮助你更好地理解和应用回溯算法。

题目来源：. - 力扣（LeetCode）

题目思路分析

代码:

注释详解

知识点摘要

相关文章：