本文目录 ⌄
题目
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
分析
回溯是一种通过穷举所有可能情况来找到所有解的算法。如果一个候选解最后被发现并不是可行解，回溯算法会舍弃它，并在前面的一些步骤做出一些修改，并重新尝试找到可行解。
可以使用回溯法，通过递归构造一棵二叉树，从而得到所有情形，这道题是不需要回退的，因为没有限制条件，仅仅递归即可。
题解
/*
* @lc app=leetcode.cn id=17 lang=cpp
*
* [17] 电话号码的字母组合
*/
// @lc code=start
class Solution {
public:
map<int, string> mp = {{'2', "abc"}, {'3', "def"}, {'4', "ghi"},
{'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"},
{'8', "tuv"}, {'9', "wxyz"}};
string str; //临时存储答案
vector<string> ans;
vector<string> letterCombinations(string digits) {
if(digits.size()==0){
return ans;
}
dfs(0,digits);
return ans;
}
void dfs(int n, string digits) {
if (n == digits.size()) {
ans.push_back(str);
return;
}
for (int i = 0; i < mp[digits[n]].size(); i++) {
str.push_back(mp[digits[n]][i]);
dfs(n+1,digits); //进入下一层
str.pop_back(); //回退最后一种情况,加入其他字母
}
}
};
// @lc code=end