Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example:
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
这题就是 简单的组合。 然而排列组合我就只会递归的写法。。。。-___-
在每个位置上， 我们都对每一种可能递归展开。
比如_Combinations("23",0,"") 也就是 "23"[0] 位置上有“abc”三种可能，那我们就递归
- _Combinations("23",1,"a")
//"23"[1] 的位置上有“def” 3中可能
1.1 _Combinations("23",2,"ad")
1.2 _Combinations("23",2,"ae")
1.3 _Combinations("23",2,"af") - _Combinations("23",1,"b")
........ - _Combinations("23",1,"c")
........
递归出口也很简单 .
代码如下。
#include <unordered_map>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
vector<string> letterCombinations(string digits) {
if (digits.empty()){
return ans;
}
_Combinations(digits,0,"");
return ans;
}
private:
unordered_map<char,string> _up={
{'2',"abc"},
{'3',"def"},
{'4',"ghi"},
{'5',"jkl"},
{'6',"mno"},
{'7',"pqrs"},
{'8',"tuv"},
{'9',"wxyz"}
};
vector<string> ans;
void _Combinations(string& digits, int cur, string comb){
if ( cur >= digits.size()){
ans.push_back(comb);
return;
}
for(auto le: _up[digits[cur]]){
_Combinations(digits,cur+1,comb + le);
}
}
};
image.png
