Leetcode|组合|17. 电话号码的字母组合（无脑回溯）

1 无脑回溯

题目简单，不需任何技巧，直接套用回溯模板即可 【吐槽】：题目有一点没有说清楚，比如提供的输入digits里面是否有重复数字？以及输出结果中的ad是否等于da？，既然不要求顺序输出，而且返回的是组合而非排列，那么只输出da而不输出ad应该是对的，但实测错误，个人以为案例没有给全

代码语言：javascript复制

class Solution {
private:
    int size;
    vector<string> solution;
    string path;
    unordered_map<char, string> num2str = {{'2', "abc"}, {'3', "def"}, {'4', "ghi"}, 
                {'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}};
public:
    void backtrack(string digits, int count) {
        if (count > size) return;
        if (count == size) {
            solution.emplace_back(path);
            return;
        }
        string str = num2str[digits[count]];
        for (int i = 0; i < str.size(); i  ) {
            path.push_back(str[i]);
            backtrack(digits, count   1);
            path.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        size = digits.size();
        backtrack(digits, 0);
        return solution;
    }
};

digits 技巧

0 人点赞