leetcode 17 电话号码的字母组合

题目

leetcode 17 电话号码的字母组合

分析

• 定义： 输入的 string digits 为节点组成的 char数据
• 解空间： 2～9键中的字母
• 终止条件： 路径的长度 == 节点数组的长度
• 解的判断条件： 终止条件就是解条件
• 不需要减枝

code

class Solution {
    void backtrace(const string& digits,vector<string>&table ,vector<string>&res,string&tmp,int cur){
        if(tmp.size() == digits.size()){
            res.push_back(tmp);
            return;
        }
        for(int i =0;i < table[digits[cur] - '2'].size();++i){
            tmp.push_back(table[digits[cur] - '2'][i]);
            backtrace(digits,table,res,tmp,cur+1);
            tmp.pop_back();
        }
    }
public:
    vector<string> letterCombinations(string digits) {
        if(digits.empty()) return {};
        vector<string> table{{"abc"},{"def"},{"ghi"},{"jkl"},{"mno"},{"pqrs"},{"tuv"},{"wxyz"}};
        vector<string> result;
        string tmp;
        backtrace(digits,table,result,tmp,0);
        return result;
        
    }
};