LeetCode-17 电话号码的字母组合

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'] 的一个数字。

solution

采用回溯

1. 建立哈希表，完成对应数字到对应字符串的映射
2. 通过回溯算法遍历每一种可能

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> res;
        string str;
        int l = digits.length();
        if (l == 0) {
            return res;
        }
        unordered_map<char, string> numcharmap{
                {'2', "abc"},
                {'3', "def"},
                {'4', "ghi"},
                {'5', "jkl"},
                {'6', "mno"},
                {'7', "pqrs"},
                {'8', "tuv"},
                {'9', "wxyz"}
        };
        backtrack(res, str, digits, numcharmap, 0);
        return res;
    }

    void backtrack(vector<string> &res, string str, string digits, unordered_map<char, string> numcharmap, int n) {
        if (str.length() == digits.length()) {
            res.push_back(str);
            return;
        } else if (n>=digits.length())
        {
            return;
        }
        char c = digits[n];
        string letters = numcharmap.at(c);
        for (int i = 0; i < letters.length(); ++i) {
            char letter = letters[i];
            backtrack(res, str + letter, digits, numcharmap, n + 1);
        }
    };
};
//leetcode submit region end(Prohibit modification and deletion)

int main() {
    Solution solution;
    solution.letterCombinations("23");
}