自学内容网 自学内容网

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 中移除最后添加的字母。
  1. 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;
}
  1. 代码仓库地址letterCombinations

原文地址:https://blog.csdn.net/yanceyxin/article/details/140425439

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!