外贸 礼品 网站,民非企业网站建设费怎么记账,临安营销型网站建设,如何选择网站做站方向题目#xff1a;
给定一个仅包含数字 2-9 的字符串#xff0c;返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下#xff08;与电话按键相同#xff09;。注意 1 不对应任何字母。
示例 1#xff1a; 输入#xff1a;digits “23”…题目
给定一个仅包含数字 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’] 的一个数字。 思路
数字和字母如何映射
首先要解决的问题是数字和字母如何映射可以使用map或者定义一个二维数组例如string letterMap[10]来做映射这里定义一个二维数组代码如下
// 数字和字母映射
const string letterMap[10] {, // 0, // 1abc, // 2def, // 3ghi, // 4jkl, // 5mno, // 6pqrs, // 7tuv, // 8wxyz // 9
};回溯法来解决n个for循环的问题
例如输入“23”抽象为树形结构如图所示 图中可以看出遍历的深度就是输入23的长度而叶子节点就是我们要收集的结果输出[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”]。
回溯三部曲
确定回溯函数参数
首先需要一个字符串path来收集叶子节点的结果然后用一个字符串数组result保存起来这两个变量我依然定义为全局。
再来看参数参数指定是有题目中给的string digits然后还要有一个参数就是int型的index。
注意这个index可不是77.组合 中等中的startIndex了。
这个index是记录遍历第几个数字了就是用来遍历digits的题目中给出数字字符串同时index也表示树的深度。
代码如下
vectorstring result;
string path;
void backtracking(const string digits, int index)确定终止条件
例如输入用例23两个数字那么根节点往下递归两层就可以了叶子节点就是要收集的结果集。
那么终止条件就是如果index 等于 输入的数字个数digits.size了本来index就是用来遍历digits的。
然后收集结果结束本层递归。
代码如下
if (index digits.size()) {result.push_back(s);return;
}确定单层遍历逻辑
首先要取index指向的数字并找到对应的字符集手机键盘的字符集。
然后for循环来处理这个字符集代码如下
int digit digits[index] - 0; // 将index指向的数字转为int
string letters letterMap[digit]; // 取数字对应的字符集
for(int i 0; i letters.size(); i){path.push_back(letters[i]); // 处理backtracking(digits, index 1); // 递归path.pop_back(); // 回溯
}注意这里for循环可不像是在回溯算法求组合问题77.组合 中等中从startIndex开始遍历的。
因为本题每一个数字代表的是不同集合也就是求不同集合之间的组合而77.组合 中等是求同一个集合中的组合 代码
class Solution {
public:// 数字和字母映射const string letterMap[10] {, // 0, // 1abc, // 2def, // 3ghi, // 4jkl, // 5mno, // 6pqrs, // 7tuv, // 8wxyz // 9};vectorstring result;string path;// charMap为当前数字对应的字母字符串void backtracking(const string digits, int index){if(digits.size() 0) return;if(index digits.size()){result.push_back(path);return;}int digit digits[index] - 0; // 将index指向的数字转为intstring letters letterMap[digit]; // 取数字对应的字符集for(int i 0; i letters.size(); i){path.push_back(letters[i]); // 处理backtracking(digits, index 1); // 递归path.pop_back(); // 回溯}}vectorstring letterCombinations(string digits) {backtracking(digits, 0);return result;}
};总结
时间复杂度: O(3^m * 4^n)其中 m 是对应三个字母的数字个数n 是对应四个字母的数字个数 空间复杂度: O(3^m * 4^n)
本并重点强调了和前面讲解过的77.组合 中等的区别本题是多个集合求组合所以在回溯的搜索过程中都有一些细节需要注意的。 参考
代码随想录
