17. 电话号码的字母组合（回溯/DFS）

Ston.V

已于 2022-03-02 23:25:07 修改

阅读量157

点赞数

分类专栏： leetcode 文章标签：深度优先算法

于 2022-03-01 22:53:00 首次发布

本文链接：https://blog.csdn.net/badmer/article/details/123218473

版权

leetcode 专栏收录该内容

25 篇文章

订阅专栏

该博客介绍了一种使用回溯法（DFS）解决字符串问题的方法，具体是根据给定的数字字符串（如'23'），生成所有可能的字母组合，如'ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf'等。示例展示了空字符串和单个数字的情况，并提供了C++实现的代码片段，包括关键的回溯函数实现。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

1.Description

2.Example

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：

输入：digits = ""
输出：[]
示例 3：

输入：digits = "2"
输出：["a","b","c"]

3. Code

回溯法（DFS）:回溯都是一个模板，写几遍就晓得了。某处有多种选择时，for遍历；开始一轮后先检查边界条件收集结果，结束一轮后回退。

class Solution {
public:
    map<char,string> m= {
        {'2',"abc"},{'3',"def"},{'4',"ghi"},{'5',"jkl"},{'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"}
    };
    int index =0;
    vector<string> res;
    string s = "";
    vector<string> letterCombinations(string digits) {
        int n = digits.length();
        if(n==0)
            return res;
        DFS(digits,index,s);
        return res;
    }
    void DFS(string digits,int index,string &s){
        if(index == digits.length()){
            res.push_back(s);
            return;
        }else{
            for(char c:m[digits[index]]){
                s.push_back(c);
                DFS(digits,index+1,s);
                s.pop_back();
            }
        }

    }
};