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.
1. Backtracking:
My first answer was wrong and I started to realize I hadn't quite understood the essence of backtracking.
http://stackoverflow.com/questions/27069642/passing-parameter-recursion-c-letter-combinations-of-a-phone-number
class Solution {
public:
const vector<string> keyboard { " ", "", "abc", "def", // '0','1','2',...
"ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
vector<string> letterCombinations(string digits) {
vector<string> res;
string combo;
bt( res, combo,digits);
return res;
}
void bt(vector<string> &res, string combo, string digits)
{
int i=combo.size();
int len =digits.size();
if ( i == len)
{
res.push_back(combo);
return;
}
int idx = digits[i] - '0';
string tmp = keyboard[idx];
int s = tmp.size();
for (int j = 0; j<s; j++)
{
bt(res, combo + tmp[j], digits);
}
}
};
2. Iterative
class Solution {
public:
const vector<string> keyboard { " ", "", "abc", "def", // '0','1','2',...
"ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
vector<string> letterCombinations(string digits) {
vector<string> res(1, "");
string combo;
int n=digits.size();
vector<string> tmp;
for(int i=0; i<n; i++)
{
int m = keyboard[digits[i]-'0'].size();
int rsize =res.size();
for (int k=0; k<rsize; k++)
{
string ts = res[k];
for (int j=0; j<m; j++)
{
res[k] = res[k] + keyboard[digits[i]-'0'][j];
tmp.push_back(res[k]);
res[k] = ts;
}
}
res = tmp;
tmp.clear();
}
return res;
}
};
No comments:
Post a Comment