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

电话号码的字母组合

题目

给定一个仅包含数字 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'] 的一个数字。

思路

深度优先遍历

class Solution {
public:
    string map[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> res; // 用来保存结果
    string tmp; // 用来保存每个分支
    vector<string> letterCombinations(string digits) {
        if(digits.size() == 0) return res;
        dfs(digits, 0);
        return res;
    }

    void dfs(string &str, int i) {
        if (i == str.size()){ // 遍历到头了，将tmp存入res中，然后返回上一级
            res.push_back(tmp);
            return;
        }
        for (int j = 0; j < map[str[i] - '0'].size(); j++) {
            tmp += map[str[i] - '0'][j];
            // 遍历下一个字符
            dfs(str, i + 1);
            tmp.pop_back();
        }
    }
};