安徽政府网站建设郑承乾付费内容网站

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");
}