算法-回溯篇03-电话号码的字母组合

电话号码的字母组合

力扣题目链接

题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

解题思路

这道题目做好数字和字母的映射就好了，其他的地方并不是很难。

过程如下：

• 定义一个map，记录下数字和字母的映射；
• 每次取第一个数字，遍历该数字对应的所有字母，然后把该数字删除；
• 这样一层递归就完成了，然后依次递归下去，直到数字全部删除。

题解

class Solution {
public:
    vector<string> ans;
    unordered_map<char, string> um = {
        {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"}, {'6', "mno"}, 
        {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
    };
    string path;

    void backTracking(string digits){
        if(digits.size() == 0){
            ans.push_back(path);
            return;
        }

        char c = digits[0];
        digits.erase(digits.begin());

        string s = um[c];
        for(int i = 0; i < s.size(); i++){
            path.push_back(s[i]);
            backTracking(digits);
            path.pop_back();
        }

        return;
    }

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

总结

这道题目我这种解法效率很低，应该是因为我使用了unordered_map并且没有剪枝，我在阅读了一些答案的写法，并没有看到明显的复杂度上的区别。