17. 电话号码的字母组合

简介: 17. 电话号码的字母组合

题目描述

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

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

解题思路

这个题目显然直接枚举就可以,那么我们现在考虑的是如何进行枚举。

我们先枚举一下:

我们要的是ad,ae…。

这不就相当于中序遍历嘛。

那么我们就可以用递归的方式来求这个字符串了。

注意全局变量,参数,函数返回值的设计。

代码

class Solution {
        unordered_map<char,string> hash={
            {'2',"abc"},
            {'3',"def"},
            {'4',"ghi"},
            {'5',"jkl"},
            {'6',"mno"},
            {'7',"pqrs"},
            {'8',"tuv"},
            {'9',"wxyz"}
        };
        vector<string> ret;
public:
    vector<string> letterCombinations(string digits) {
        if(digits.size()==0) return {};
        dfs(digits,0,"");
        return ret;
    }
    void dfs(string& digits,int pos,string s)
    {
        if(pos>=digits.size())
        {
            ret.push_back(s);
            return ;
        } 

        for(auto ch:hash[digits[pos]])
        {
            dfs(digits,pos+1,s+ch);
        }
        
    }
};
相关文章
|
1月前
|
算法
【LeetCode 52】17.电话号码的字母组合
【LeetCode 52】17.电话号码的字母组合
31 0
|
3月前
|
算法
LeetCode第17题电话号码的字母组合
该文章介绍了 LeetCode 第 17 题电话号码的字母组合的解法,通过分析得出可使用递归和回溯的思想解决,避免循环穷举的高循环次数,并给出了具体的编码实现,同时总结了该题较难理解,需要了解递归的本质,当嵌套循环层次多时可考虑递归。
LeetCode第17题电话号码的字母组合
|
5月前
17. 电话号码的字母组合
17. 电话号码的字母组合
|
6月前
|
存储 算法
17.电话号码的字母组合
17.电话号码的字母组合
35 0
|
6月前
|
Java
leetcode-17:电话号码的字母组合
leetcode-17:电话号码的字母组合
36 0
leetcode-17:电话号码的字母组合
|
11月前
|
存储 C++ 索引
电话号码的字母组合(C++实现)
电话号码的字母组合(C++实现)
68 0
|
机器学习/深度学习 算法 安全
LeetCode - #17 电话号码的字母组合
不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言,我们会尽力满足大家的需求。
103 0
leetcode:17.电话号码的字母组合
可以抽象成一个排列组合的问题,题目的意思就是说当输入"23"的时候实际上就是按了两次按键,分别是2和3,然后2对应的是abc,3对应的是def,所以我们只需递归遍历每一种结果即可解决问题。
43 0
leetcode:17.电话号码的字母组合