LeetCode 算法：电话号码的字母组合 c++

原题链接🔗：电话号码的字母组合
难度：中等⭐️⭐️

题目

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

示例 2：
输入：digits = “”
输出：[]

示例 3：
输入：digits = “2”
输出：[“a”,“b”,“c”]

提示：

• 0 <= digits.length <= 4
• digits[i] 是范围 [‘2’, ‘9’] 的一个数字。

题解

1. 解题思路：

LeetCode 上的 “电话号码的字母组合” 问题要求你根据一个数字电话号码，生成所有的可能的字母组合。在这个问题中，每个数字键对应一组字母，例如：

• 2 对应 ‘a’, ‘b’, ‘c’
• 3 对应 ‘d’, ‘e’, ‘f’
• …

解题思路如下：

1. 理解问题：首先，要清楚每个数字键对应的字母组合，以及电话号码可能的组合方式。

2. 回溯法：这是一个典型的回溯问题，我们可以使用回溯法来解决。回溯法是一种通过递归来搜索所有可能解的方法。

3. 构建映射：创建一个映射，将每个数字键映射到它对应的字母组合。

4. 递归生成组合：使用递归函数，每次递归调用时，尝试当前数字键的所有可能字母，并将其添加到当前的组合中。

5. 回溯：在递归过程中，如果当前组合的长度等于电话号码的长度，说明找到了一个有效的组合，将其添加到结果中。然后回溯，移除当前添加的字母，尝试下一个字母。

6. 优化：在生成组合的过程中，如果当前数字键没有对应的字母，直接回溯到上一个数字键。

下面是这个问题的一般性解题步骤：

• 定义一个映射 digitToChar，将每个数字映射到对应的字母字符串。
• 定义一个递归函数 backtrack，接收当前的组合 current，当前处理的数字索引 index，以及电话号码 digits 作为参数。
• 在 backtrack 函数中，如果 index 等于电话号码的长度，将当前的组合 current 添加到结果 result 中。
• 对于当前索引 index，获取当前数字对应的所有字母，然后对每个字母进行递归调用 backtrack，并将字母添加到当前组合 current 中。
• 在递归调用后，需要回溯，即从 current 中移除最后添加的字母。

2. c++ demo：

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> combinations;
        if (digits.empty()) {
            return combinations;
        }
        unordered_map<char, string> phoneMap{
            {'2', "abc"},
            {'3', "def"},
            {'4', "ghi"},
            {'5', "jkl"},
            {'6', "mno"},
            {'7', "pqrs"},
            {'8', "tuv"},
            {'9', "wxyz"}
        };
        string combination;
        backtrack(combinations, phoneMap, digits, 0, combination);
        return combinations;
    }

    void backtrack(vector<string>& combinations, const unordered_map<char, string>& phoneMap, const string& digits, int index, string& combination) {
        if (index == digits.length()) {
            combinations.push_back(combination);
        }
        else {
            char digit = digits[index];
            const string& letters = phoneMap.at(digit);
            for (const char& letter : letters) {
                combination.push_back(letter);
                backtrack(combinations, phoneMap, digits, index + 1, combination);
                combination.pop_back();
            }
        }
    }
};


int main() {
    Solution solution;
    std::string digits = "23";
    std::vector<std::string> combinations = solution.letterCombinations(digits);

    for (const std::string& combination : combinations) {
        std::cout << combination << std::endl;
    }
    return 0;
}

3. 代码仓库地址：letterCombinations