leetcode17. 电话号码的字母组合

一:题目

leetcode17. 电话号码的字母组合

二:思路

1.分析题意这个我们输入的数字字符串,每个数字代表的是一个字符串,我们就可以将其设置为一层需要
遍历的字符串,所以我们就可以知道,我们遍历出的每个字符组合的长度等于(我们输入的数字字符串
的大小)

我们需要定义一个字符串数组
const string mp[10] = {
“”,//0
“”,//1
“abc”,//2
“def”,//3
“ghi”,//4
“jkl”,//5
“mno”,//6
“pqrs”,//7
“tuv”,//8
“wxyz”,//9
};

2.回溯的三步曲
vectorans;//存放最终的结果
string s;记录一次深次遍历的结果
1>:确定回溯函数的参数
//这里的index记录我们遍历到我们的输入第几个数字(也就是树的深度)
void backstacking(string &digits,int index)

2>:确定终止条件
if(s.size() == index){
ans.push_back(s);
return;
}
3>:确定单层遍历逻辑
int temp = digits[index] - ‘0’;//确定我们输入的字符串的第一个数字
string str = mp[temp];//确定我们的字符串是啥
for(int i = 0; i < str.size(); i++) {
s.push_back(str[i]);
backstacking(digits,index+1);
s.pop_back();
}

三:上码

class Solution {
public:

    /**
        思路:
        1.分析题意这个我们输入的数字字符串,每个数字代表的是一个字符串,我们就可以将其设置为一层需要
          遍历的字符串,所以我们就可以知道,我们遍历出的每个字符组合的长度等于(我们输入的数字字符串
          的大小)

        我们需要定义一个字符串数组
        const string mp[10] = {
            "",//0
            "",//1
            "abc",//2
            "def",//3
            "ghi",//4
            "jkl",//5
            "mno",//6
            "pqrs",//7
            "tuv",//8
            "wxyz",//9
        };

        2.回溯的三步曲
            vector<string>ans;//存放最终的结果
            string s;记录一次深次遍历的结果
          1>:确定回溯函数的参数
            //这里的index记录我们遍历到我们的输入第几个数字(也就是树的深度)
            void backstacking(string &digits,int index)        

          2>:确定终止条件
            if(s.size() == index){
                ans.push_back(s);
                return;
            }
          3>:确定单层遍历逻辑  
            int temp = digits[index] - '0';//确定我们输入的字符串的第一个数字
            string str = mp[temp];//确定我们的字符串是啥
            for(int i = 0; i < str.size(); i++) {
                s.push_back(str[i]);
                backstacking(digits,index+1);
                s.pop_back();
            }    
    */
     const string mp[10] = {
            "",//0
            "",//1
            "abc",//2
            "def",//3
            "ghi",//4
            "jkl",//5
            "mno",//6
            "pqrs",//7
            "tuv",//8
            "wxyz",//9
    };
    vector<string>ans;//存放最终的结果
    string s;//记录一次深次遍历的结果

     void backstacking(string &digits,int index) {
        if(digits.size() == index){//当递归的深度等于我们的输入的字符串长度
            ans.push_back(s);
            return;
        }

        int temp = digits[index] - '0';//确定我们输入的字符串的第一个数字
        string str = mp[temp];//确定我们的字符串是啥
        for(int i = 0; i < str.size(); i++) {
            s.push_back(str[i]);
            backstacking(digits,index+1);
            s.pop_back();
        }    

     }  

    vector<string> letterCombinations(string digits) {
        
        if(digits.size() == 0 ){
            return {};
        }

        backstacking(digits,0);
        
        return ans;
    }
};

leetcode17. 电话号码的字母组合
加油 感觉还有很多东西要学 自己也觉得无从下手 可是又能怎样呢 放弃? 不可能 都坚持这么久了 那就去做吧 一点点来 该来会来的 该有的会有的 好的东西 需要足够优秀才能配得上 何必去在乎眼见的得失呢 加油 菜鸡杰 加油 菜鸡杰
加油菜鸡杰 你是最棒的

上一篇:56. 合并区间


下一篇:887. 鸡蛋掉落