首页 > 其他 > 详细

LeetCode 017. 电话号码的字母组合  dfs

时间:2020-08-26 15:29:28      阅读:85      评论:0      收藏:0      [点我收藏+]

地址 https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。


示例:

输入:"23"
输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

算法1
DFS做法 从每个数字对应的元素中选出一个 然后进入下一层
最终每层中都选出一个对应的元素 则组合成一个答案

class Solution {
public:

    map<char, string> m = {
    {2,"abc"},{3,"def"},
    {4,"ghi"},{5,"jkl"},
    {6,"mno"},{7,"pqrs"},
    {8,"tuv"},{9,"wxyz"}
};

vector<string> ans;

void dfs(string s, string digits, int idx)
{
    if (idx == digits.size()) {
        ans.push_back(s);
        return;
    }
    char digt = digits[idx];
    for (int j = 0; j < m[digt].size(); j++) {
        s += m[digt][j];
        dfs(s, digits,idx + 1);
        s.pop_back();
    }
}

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

    return ans;
}


};

 

LeetCode 017. 电话号码的字母组合  dfs

原文:https://www.cnblogs.com/itdef/p/13565125.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!