一 🏠 题目描述
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}
如上例所示,对于任意一位(首中末),它们都需要保持字符变更直至结果集遍历结束 🐳🐳🐳
四 🏠 心路历程
为方便各位看官大大了解博主真实刷题过程,我把当时状态纯纯真实还原,记录在心路历程这一小节,不感兴趣的小伙伴可以直接跳过哈
博主在第一阶段提取 🚀 关键信息没有问题,在第二阶段 🚀 思路整理没有问题,上述实现和题解是博主原创