【LeetCode热题100】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’] 的一个数字。

四.解题思路

start变量用来控制每一层递归该处理原字符串哪个位置的数，第二个for为了穷举每一层可以取到的所有字母

五.代码实现

class Solution {
public:
    unordered_map<char, string> hashmap = {
        {'2', "abc"}, {'3', "def"},  {'4', "ghi"}, {'5', "jkl"},
        {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}};

    vector<string> letterCombinations(string digits) {
        vector<string> ans;
        string path;
        dfs(ans, path, digits, 0);
        return ans;
    }

    void dfs(vector<string>& ans, string& path, string digits, int start) {
        if (digits.empty())
            return;

        if (path.size() == digits.size()) {
            ans.push_back(path);
            return;
        }

        for (int i = start; i < digits.size(); i++) {
            for (int j = 0; j < hashmap[digits[i]].size(); j++) {
                path += hashmap[digits[i]][j];
                dfs(ans, path, digits, i + 1);
                path.pop_back();
            }
        }
    }
};