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

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

题目

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

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：

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

输入：digits = “”
输出：[]
示例 3：

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

提示：

0 <= digits.length <= 4
digits[i] 是范围 [‘2’, ‘9’] 的一个数字。
leetcode 17 电话号码字母组合,# 我得leetcode之路,leetcode,深度优先,算法

概述

这是一道dfs的题目
首先为什么他是一道dfs的题目？
dfs是一个遍历的方式，该题就是按键映射的字母的排列组合，所以这道题就是一道dfs的题目
怎么处理dfs的题目？
对于dfs的题目处理方式：
1.写出终止条件
2.候选节点的筛选
3.回溯

代码

class Solution {
public:
    string temp;
    // 注意审题，前面两个用不到，所以置为空串
    vector<string> board = {"", "", "abc", "def", "ghi","jkl","mno","pqrs","tuv","wxyz"};
    // 用来存放结果的空串
    vector<string> ans;
    void dfs(int pos,string digits){
        //1. 终止条件
        if(pos==digits.size()){
            ans.push_back(temp);
            return;
        }
        // 候选节点的筛选
        // 表示键盘按到了第几个键
        int nums=digits[pos]-'0';
        for(int i=0;i<board[nums].size();i++){
            temp.push_back(board[nums][i]);
            dfs(pos+1,digits);
            temp.pop_back();//回溯
        }
    }

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