我又来水博客了
这次水的原因是因为5分钟内写出了执行用时和内存消耗都战胜百分百用户的一道中等
题(依旧菜鸡),也是在LeetCode中第一道通过自己能力写出来的双百题(其实也没做几道)
但是显而易见这依旧是一题水题
题目如下
题目
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
相信大家都用过以前那种老式的固定电话,数字键上除了数字还有对应的符号与字母(我寻思这不是九键拼音么),因此现在我们需要做的就是,给定数字字符串,给出他们所有的排列组合
比如输入"23"
输出["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
因为2对应的字母有'abc',3对应的字母为'def',因此排列组合显而易见
但是通过程序要如何解决呢?
解题思路
很多人肯定很快就会想到,用for循环依次遍历啊,其实这个思路是对的,但需要解决的问题是,给定的字符串长度不定,如果你的字符串固定长度为3,则可以直接暴力3个for出结果,但是长度可变,这个暴力显然无法凑效
此时,递归的魅力就出来了
我们首先在函数中定义一个空字符串,然后对这个字符串使用for循环依次加上对应位置的字符,比如初始状态空字符,第一个原始字符是'2',那我们用for循环遍历就分别得到了"a","b","c"三个字符串
随后在调用函数进行递归,通过下一位原始字符进行读取,比如下一个字符是'3',那我们就得到了"ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"这几个字符串,以此类推,一旦字符串长度与原始数字串长度相等,则直接扔到结果容器中,并且return终止这一条线
AC代码
class Solution {
public:
vector<string> result;
char a[9][4]={{},{'a','b','c'},{'d','e','f'},{'g','h','i'},{'j','k','l'},{'m','n','o'},{'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}}; //定义每个原始字符对应的字母
int num[9]={0,3,3,3,3,3,4,3,4}; //定义每个原始字符对应的字母数
void perm(string yuan,string str1) //递归函数定义
{
//倘若当前字符串与原始数字串长度相等,将字符串扔到容器中,返回
if(str1.length()==yuan.length())
{
result.push_back(str1);
return;
}
for(int i=0;i<num[yuan[str1.length()]-'0'-1];i++) //对原始字符对应的字母进行遍历,比如2的话就依次遍历abc
perm(yuan,str1+a[yuan[str1.length()]-'0'-1][i]); //将当前字符串加上字母后,递归操作
}
vector<string> letterCombinations(string digits) {
if(!digits.length()) //应对空数字字符的坑爹情况
return result;
perm(digits,""); //递归操作
return result; //返回结果
}
};
总结
菜鸡固然是菜鸡,但是多做题还是会变成稍微有点水平的菜鸡的,递归牛逼
Q.E.D.
Comments | 0 条评论