刷爆力扣之电话号码的字母组合

简介: 刷爆力扣之电话号码的字母组合

一 🏠 题目描述

17. 电话号码的字母组合


给定一个仅包含数字 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 <=4digits[i] 是范围 ['2', '9'] 的一个数字。


二 🏠破题思路

2.1 🚀 关键信息

解决问题第一步,当然先提取题目字面上的关键信息 😎😎😎


以任意的三个序列举例, {a, b} , {c, d} , {e, f} ,它们的所能表示的字母组合为 🌼🌼🌼


{a, c, e} {b, c, e}
{a, c, f} {b, c, f}
{a, d, e} {b, d, e}
{a, d, f} {b, d, f}

很容易发现规律,对于任意三个序列的字母组合(假设它们元素个数分别为,X1 个元素, X2 个元素, X3 个元素),它们当前序列字母变化规律为首位字母为 X1 * X2 * X3 / X1,第二位字母的变化规律为 X1 * X2 * X3 / X1 * X2,第三位字母的变化规律为 X1 * X2 * X3 / X1 * X2 * X3 = 1 🌻🌻🌻



提取完题目中的关键信息后,直接进入第二阶段,思路整理 😃😃😃



2.2 🚀 思路整理

偏移法


由关键信息可把上述规律推广至任意个数的序列 🌹🌹🌹


首先使用哈希表存储每个数字对应的所有可能的字母,构造出所有的字母组合(各序列元素个数相乘)


遍历数字串,找到哈希表的映射并按照上述字母的变化规律把结果字符串依次连接,最后返回结果集 🌺🌺🌺


注:回溯法 ,感兴趣的小伙伴可以了解一下



整理完解题思路后,直接进入第三阶段,代码实现 😃😃😃



三 🏠 代码详解

3.1 🚀 代码实现

按照我们刚才的破题思路,直接代码走起来 👇👇👇👇


std::unordered_map<char, std::vector<char>> digitMap = {
        { '2', { 'a', 'b', 'c' } }, { '3', { 'd', 'e', 'f' } }, { '4', { 'g', 'h', 'i' } },
        { '5', { 'j', 'k', 'l' } }, { '6', { 'm', 'n', 'o' } }, { '7', { 'p', 'q', 'r', 's' } },
        { '8', { 't', 'u', 'v' } }, { '9', { 'w', 'x', 'y', 'z' } } };
vector<string> letterCombinations(string digits) {
    int resCount =1;
for (auto& i : digits) resCount *= digitMap[i].size(); //求出一共有多少条结果集
    std::vector<std::string> resVec(resCount); //初始化结果集
    int offsets = resCount; //定义偏移量
for (auto& i : digits) {
        int digitVecLen = digitMap[i].size(); //当前数字对应的字母数
        offsets = offsets / digitVecLen; //计算偏移量
        int digitVecIndex =0, currOffsets =0; //初始化digitVec索引和当前偏移量
for (auto& str : resVec) { //遍历结果集
if (currOffsets == offsets) { //如果当前移动等于偏移量
                currOffsets =0; //当前偏移置为 0if (digitVecIndex == digitVecLen -1) digitVecIndex =0; //到达数组末尾重头开始
else++digitVecIndex; //索引加加
            }
            str += digitMap[i][digitVecIndex]; //连接当前字符
++currOffsets; //移动当前偏移
        }
    }
    return resCount !=1 ? resVec : vector<string>(); //返回结果集
}



3.2 🚀 细节解析

看完 👀👀👀 全注释版的代码实现后,相信看官大大对整体逻辑已经是大写的 OK 了 😃😃😃


那么我们挖掘上述实现的晦涩细节 😖😖😖 进行解析,直接开干,走起来 👇👇👇👇


offsets = offsets / digitVecLen; //计算偏移量

这里的偏移量即为字母变化规律,代表间隔多少个元素后,当前序列字符进行变更


例,首位字母为 X1 * X2 * X3 / X1,末位字母为 X1 * X2 * X3 / X1 * X2 * X3 = 1 🐌🐌🐌



if (digitVecIndex == digitVecLen -1) digitVecIndex =0; //到达数组末尾重头开始

只有当遍历结果集结束时,当前序列字符进行变更才算结束


{a, c, e} {a, c, f} {a, d, e} {a, d, f} {b, c, e} {b, c, f} {b, d, e} {b, d, f}


如上例所示,对于任意一位(首中末),它们都需要保持字符变更直至结果集遍历结束 🐳🐳🐳



四 🏠 心路历程

为方便各位看官大大了解博主真实刷题过程,我把当时状态纯纯真实还原,记录在心路历程这一小节,不感兴趣的小伙伴可以直接跳过哈


博主在第一阶段提取 🚀 关键信息没有问题,在第二阶段 🚀 思路整理没有问题,上述实现和题解是博主原创


相关文章
|
5月前
|
存储 算法
LeetCode第49题字母异位词分组
LeetCode第49题"字母异位词分组"的解题方法,通过将每个字符串的字符排序后作为键存储在HashMap中,有效地将所有字母异位词分组。
LeetCode第49题字母异位词分组
|
3月前
|
存储
Leetcode第49题(字母异位词分组)
LeetCode第49题要求将字符串数组中的字母异位词分组,可以通过将每个字符串排序后作为键存入哈希表,最后将哈希表中的值添加到结果列表中来实现。
25 1
|
3月前
|
算法
Leetcode第十七题(电话号码的字母组合)
这篇文章介绍了如何使用深度优先搜索(DFS)算法来解决LeetCode第17题——电话号码的字母组合问题,通过递归方法生成所有可能的字母组合。
27 0
Leetcode第十七题(电话号码的字母组合)
|
3月前
|
索引
【LeetCode 11】242.有效的字母异位词
【LeetCode 11】242.有效的字母异位词
21 0
【LeetCode 11】242.有效的字母异位词
|
3月前
|
算法
【LeetCode 52】17.电话号码的字母组合
【LeetCode 52】17.电话号码的字母组合
43 0
|
5月前
|
算法
LeetCode第17题电话号码的字母组合
该文章介绍了 LeetCode 第 17 题电话号码的字母组合的解法,通过分析得出可使用递归和回溯的思想解决,避免循环穷举的高循环次数,并给出了具体的编码实现,同时总结了该题较难理解,需要了解递归的本质,当嵌套循环层次多时可考虑递归。
LeetCode第17题电话号码的字母组合
|
7月前
|
算法 容器
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
|
7月前
|
存储
力扣经典150题第四十二题:字母异位词分组
力扣经典150题第四十二题:字母异位词分组
43 0
|
7月前
|
存储
力扣经典150题第四十一题:有效的字母异位词
力扣经典150题第四十一题:有效的字母异位词
40 0
|
7月前
|
算法
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成