【DFS】LeetCode 17. 电话号码的字母组合

简介: 看第一个示例:输入"23",其对应的是"abc"与"de".根据全排列的特点,我们先把它们按层状结构写开,之后依次排列组合即可

Halo,这里是Ppeua。平时主要更新C语言,C++,数据结构算法…感兴趣就关注我bua!



题目:


1e65d3dfae2c4a93a63d9cddaba96df8.png



示例:


5cec6fefc0124f0e98aba909a89dfc83.png


题解:


这是一道全排列的问题,先来看看示例.


看第一个示例:输入"23",其对应的是"abc"与"de".根据全排列的特点,我们先把它们按层状结构写开,之后依次排列组合即可


具体的有:


先选取第零层(“abc”)中的一个,之后选取第一层(“de”)中的一个,这时候到了第二层,此时层数等于输入的"23"的size(),说明当前趟排列结束.则存储答案,并返回上一层开始继续下一个排列.


ad0e076adc3548b3956c24c917e2e025.jpg


下面来看看具体的代码实现:


代码实现:


#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
    string a[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; 
    void conbinStr(string digits,int level,string combine,vector<string>&v)
    {
        if(level==digits.size())
        {
            v.push_back(combine);
            return ;
        }
        int num=digits[level]-'0';
        string str=a[num];
        for(int i=0;i<str.size();i++)
        {
            conbinStr(digits,level+1,combine+str[i],v);
        }
    }
    vector<string> letterCombinations(string digits) {
        vector<string>ans;
        if(digits.size()==0)
        {
            return ans;
        }
        conbinStr(digits,0,"",ans);
        return ans;
    }
};


1.先理清整体思路,我们需要进行深搜,但是letterCombinations的参数并不能满足我们的需求,所以我们需要自定义一个函数.Digits(题给字符串), Level(层数),Combine(组合字符串),v(答案数组),我们定义一个字符串,用来对应每一个按键所带的字母


2.之后开始层状调用


e64788fcf1dd4dafa58c7e6b16ccc39f.jpg

目录
相关文章
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
4月前
|
存储 算法
LeetCode第49题字母异位词分组
LeetCode第49题"字母异位词分组"的解题方法,通过将每个字符串的字符排序后作为键存储在HashMap中,有效地将所有字母异位词分组。
LeetCode第49题字母异位词分组
|
2月前
|
存储
Leetcode第49题(字母异位词分组)
LeetCode第49题要求将字符串数组中的字母异位词分组,可以通过将每个字符串排序后作为键存入哈希表,最后将哈希表中的值添加到结果列表中来实现。
18 1
|
2月前
|
算法
Leetcode第十七题(电话号码的字母组合)
这篇文章介绍了如何使用深度优先搜索(DFS)算法来解决LeetCode第17题——电话号码的字母组合问题,通过递归方法生成所有可能的字母组合。
25 0
Leetcode第十七题(电话号码的字母组合)
|
2月前
|
索引
【LeetCode 11】242.有效的字母异位词
【LeetCode 11】242.有效的字母异位词
19 0
【LeetCode 11】242.有效的字母异位词
|
2月前
|
算法
【LeetCode 52】17.电话号码的字母组合
【LeetCode 52】17.电话号码的字母组合
42 0
|
4月前
|
算法
LeetCode第17题电话号码的字母组合
该文章介绍了 LeetCode 第 17 题电话号码的字母组合的解法,通过分析得出可使用递归和回溯的思想解决,避免循环穷举的高循环次数,并给出了具体的编码实现,同时总结了该题较难理解,需要了解递归的本质,当嵌套循环层次多时可考虑递归。
LeetCode第17题电话号码的字母组合
|
6月前
|
存储
力扣经典150题第四十二题:字母异位词分组
力扣经典150题第四十二题:字母异位词分组
40 0
|
6月前
|
存储
力扣经典150题第四十一题:有效的字母异位词
力扣经典150题第四十一题:有效的字母异位词
35 0
|
4月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
128 2