网站网页设计哪个好,有限责任公司设立条件,莫停之科技windows优化大师,备案网站主办者承诺书题目 - 点击直达 1. 17. 电话号码的字母组合 中等1. 题目详情1. 原题链接2. 题目要求3. 基础框架 2. 解题思路1. 思路分析2. 时间复杂度3. 代码实现 3. 知识与收获 1. 17. 电话号码的字母组合 中等
1. 题目详情
1. 原题链接
LeetCode 17. 电话号码的字母组合 中等
2. 题目要… 题目 - 点击直达 1. 17. 电话号码的字母组合 中等1. 题目详情1. 原题链接2. 题目要求3. 基础框架 2. 解题思路1. 思路分析2. 时间复杂度3. 代码实现 3. 知识与收获 1. 17. 电话号码的字母组合 中等
1. 题目详情
1. 原题链接
LeetCode 17. 电话号码的字母组合 中等
2. 题目要求
给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。 示例 1 输入digits “23” 输出[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”] 示例 2 输入digits “” 输出[] 示例 3 输入digits “2” 输出[“a”,“b”,“c”] 提示 0 d i g i t s . l e n g t h 4 0 digits.length 4 0digits.length4 d i g i t s [ i ] digits[i] digits[i] 是范围 [ ′ 2 ′ , ′ 9 ′ ] [2, 9] [′2′,′9′]的一个数字。
3. 基础框架
● Cpp代码框架
class Solution {
public:vectorstring letterCombinations(string digits) {}
};2. 解题思路
全排列、多叉树的前序遍历
1. 思路分析 ( 1 ) (1) (1) 首先建立数字与对应多个字符的映射 string aStr[10] {“”, “”, “abc”, “def”, “ghi”,“jkl”,“mno”,“pqrs”,“tuv”,“wxyz”}; 0和1不对应字母2-9依次对应字符串。 ( 2 ) (2) (2) 例如字符串 d i g i t s digits digits[“237”]其中的2、3、4对应的字符串分别是[“abc”]、[“def”]、[“pqrs”] 组合的结果共有 3 ∗ 3 ∗ 4 36 3*3*436 3∗3∗436种即先在[“abc”]中任取一个然后在[“def”]中任取一个最后在[“pqrs”]中任取一个即 A 3 1 ∗ A 3 1 ∗ A 4 1 A_3^1 * A_3^1 * A_4^1 A31∗A31∗A41。 ( 3 ) (3) (3) 把[“abc”]、[“def”]、[“pqrs”]分别看做多叉树的第一层、第二层、第三层 对这颗多叉树进行深度优先遍历就可以依次得到组合的结果 第一层[“abc”]首先选择第一个字符’a’第二层[“def”]选择第一个字符’d’第三层[“pqrs”]选择第一个字符’p’这样到达最后一层时相当于完成了一次深度优先遍历也得到了一种组合[“adp”]第三层共包含四个字符故需要选择四次,共得到四种组合[“adp”、“adq”、“adr”、“ads”] 之后回到第二层[“def”]选择第二个字符’e’第三层依次选择[“pqrs”]中的字符得到四种组合[“aep”、“aeq”、“aer”、“aes”] 之后再回到第二层[“def”]选择第三个字符’f’第三层依次选择[“pqrs”]中的字符得到四种组合[“afp”、“afq”、“afr”、“afs”] 这样第一层字符为’a’的所有组合都选择了一遍对第一层中’a’字符之后的剩余字符继续进行上述遍历操作得到以该字母开头的所有组合 ( 4 ) (4) (4) 多叉树的遍历本质与二叉树相同二叉树节点只有两个递归时只需递归左右子树即可多叉树节点则有多个递归时需要依次递归所有子树 ( 5 ) (5) (5) 递归函数的设计 引用类型的结果二维数组vectorstring ret 引用类型的字符串类型string digits所有栈帧都用到初始字符串参数 int类型的index当前栈帧内所在的digits的下标也代表这在第几层超过范围时类似于二叉树中节点为nullptr string类型的一种结果字符串string comStr每一层都会从当前层选择一个字符与comStr进行组合当最后一层的字符与其组合后便是一种结果该结果继续传递给最后一层的下一层在最后一层的下一层并不存在此时i是越界的函数将返回再返回之前需要把最后一层得到并传入的结果尾插到结果二维数组中
2. 时间复杂度 O ( 4 N ) O(4^N) O(4N) 范围[2, 9]数字对应的字符最少有 3 3 3个最多有 4 4 4个假设输入的数字长度为 N N N且输入的数字对应的字符都是 4 4 4个。 N N N个数字对应 N N N个长度为 4 4 4的字符串对一个长度为 4 4 4的字符串进行 4 4 4次选择则对 N N N个长度为 4 4 4的字符串进行 4 N 4^N 4N次选择。 3. 代码实现
class Solution {const static string aStr[10];
public:// 多叉树、回溯、全排列void combin(vectorstring ret, const string digits, int i, string comStr){// 递归结束条件if(i digits.size()){ret.push_back(comStr);return;}// 深度递归int index digits[i] - 0;for(int j 0; j aStr[index].size(); j){combin(ret, digits, i 1, comStr aStr[index][j]);}}vectorstring letterCombinations(string digits) {vectorstring ret;if(digits.empty()) return ret;combin(ret, digits, 0, );return ret;}
};
const string Solution::aStr[10] {, , abc, def, ghi,jkl,mno,pqrs,tuv,wxyz};3. 知识与收获 ( 1 ) (1) (1) 二叉树深度优先遍历、回溯 T h e The The E n d End End
