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

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

题目思路分析

题目要求我们将一个数字字符串（每个数字对应一组字母，如2对应abc，3对应def等）转换成所有可能的字母组合。这是一个典型的组合生成问题，可以使用回溯算法来解决。回溯算法通过递归地构建候选解并逐步扩展，如果某个候选解不符合要求，则“回溯”并尝试其他可能的候选解。

1. 初始化映射：首先，我们需要建立一个数字到字母的映射表。
2. 递归生成组合：对于输入的数字字符串，我们从第一个数字开始，依次取出其对应的字母，然后递归地处理下一个数字。
3. 回溯：在递归的过程中，当处理完一个数字的所有字母后，我们需要将最后一个添加的字母从当前组合中移除（即回溯），以便尝试下一个字母。
4. 终止条件：当处理完所有数字时，我们将当前组合添加到结果集中。

代码:

#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实现数字到字母的映射。
• 字符串操作：包括字符串的拼接和字符的移除。

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