网站开发并发处理,江门网站制作服务,专门做网站的app,贵阳建设局网站LeetCode-17 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串#xff0c;返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下#xff08;与电话按键相同#xff09;。注意 1 不对应任何字母。 示例 1#xff1a;
输入#xff1a;d…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 4digits[i] 是范围 [2, 9] 的一个数字。
solution
采用回溯
建立哈希表完成对应数字到对应字符串的映射通过回溯算法遍历每一种可能
#include string
#include vector
#include unordered_mapusing namespace std;//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:vectorstring letterCombinations(string digits) {vectorstring res;string str;int l digits.length();if (l 0) {return res;}unordered_mapchar, 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(vectorstring res, string str, string digits, unordered_mapchar, string numcharmap, int n) {if (str.length() digits.length()) {res.push_back(str);return;} else if (ndigits.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);
}
