A mapping of digit to letters (just like on the telephone buttons) is given below.
Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.
问题描述：给定一个数字串，返回这个数字串可能代表的所有字符的组合。
数字与字符的组合如上，跟手机按键类似。
这题可以用递归的方式思考，例如"23"，2表示的字符串有"a", "b", "c"，然后在每个字符串后面添加3表示的每个字符。
class Solution {
public:
vector letterCombinations(string digits) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
map phone;
phone.insert(make_pair('2', "abc"));
phone.insert(make_pair('3', "def"));
phone.insert(make_pair('4', "ghi"));
phone.insert(make_pair('5', "jkl"));
phone.insert(make_pair('6', "mno"));
phone.insert(make_pair('7', "pqrs"));
phone.insert(make_pair('8', "tuv"));
phone.insert(make_pair('9', "wxyz"));
phone.insert(make_pair('0', " "));
if(digits.size() == 0)
return vector
(1, "");
char ch = *(digits.end() - 1);
digits.erase(digits.end() - 1);
vector svec = letterCombinations(digits);
vector::size_type svec_size = svec.size();
vector::size_type i = 0;
for(i = 0; i != svec_size; ++i) {
string str = svec[i];
string tmp = svec[i];
for(string::iterator siter = phone[ch].begin();
siter != phone[ch].end(); ++siter) {
tmp = str;
svec.push_back(tmp + *siter);
}
}
for(i = 0; i != svec_size; ++i) {
svec.erase(svec.begin());
}
return svec;
}
};