leetcode 17. 电话号码的字母组合-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode 17. 电话号码的字母组合。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

2023.7.18

leetcode 17. 电话号码的字母组合,leetcode专栏,leetcode,算法,职场和发展,数据结构,c++

该题也是经典回溯题。与之前做的组合有两点不同：

之前的组合题是求同一集合的组合，而本题是求不同集合的组合。
本题还需要有一个将字符串数字转换为手机号9键对应字符集的过程。

下面上代码：

class Solution {
public:
    string letter_map[10] = {
        "",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz"
    };
    vector<string> ans;
    string path;
    void backtrating(string digits,int index)
    {
        //中止条件
        if(index == digits.size())
        {
            ans.push_back(path);
            return;
        }

        //将对应string型数字转换为int型
        int digit = digits[index]-'0';
        //取出该数字对应的字符集
        string letters = letter_map[digit];

        for(int i=0; i<letters.size(); i++)
        {
            path.push_back(letters[i]);
            backtrating(digits,index+1);
            path.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        if(digits.size() == 0) return {};
        backtrating(digits,0);
        return ans;
    }
};

如果面试中的话要注意判断异常输入的情况，即可能输入为#、0、1等异常情况。

2023.9.21

时隔两个月，二刷。遇到这种貌似能用for循环暴力解决的、但是又不知道用多少层for循环的题，就可以想想回溯了。思路和之前类似，代码稍有不同：

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if(digits.size() == 0) return {};
        vector<string> ans;
        unordered_map<char,string> hash{
            {'0'," "},
            {'1'," "},
            {'2',"abc"},
            {'3',"def"},
            {'4',"ghi"},
            {'5',"jkl"},
            {'6',"mno"},
            {'7',"pqrs"},
            {'8',"tuv"},
            {'9',"wxyz"},
            {'*'," "},
            {'#'," "}
        };
        backtrating(ans , "" , digits , hash , 0);
        return ans;
    }
    void backtrating(vector<string>& ans , string path , string& digits , unordered_map<char,string> hash , int start)
    {
        //中止条件
        if(path.size() == digits.size())
        {
            ans.push_back(path);
            return;
        }
        string letters = hash[digits[start]];
        for(char letter : letters)
        {
            path += letter;
            backtrating(ans , path , digits , hash , start+1);
            path.pop_back();
        }
    }
};

看了下之前的代码，可以将ans和path以及hash表都放在全局变量中，这样就不用传那么多参数了。回溯经典题，日后还得三刷。文章来源地址https://www.toymoban.com/news/detail-593382.html

到了这里，关于leetcode 17. 电话号码的字母组合的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！