Wednesday, May 22, 2013
Leetcode: Letter Combinations of a Phone Number in C++
Given a digit string, return all possible letter combinations that the number could represent.
Solution:
vector<char> switchchar(char input)
{
vector<char> result;
switch(input)
{
case '2':
result.push_back('a');
result.push_back('b');
result.push_back('c');
break;
case '3':
result.push_back('d');
result.push_back('e');
result.push_back('f');
break;
case '4':
result.push_back('g');
result.push_back('h');
result.push_back('i');
break;
case '5':
result.push_back('j');
result.push_back('k');
result.push_back('l');
break;
case '6':
result.push_back('m');
result.push_back('n');
result.push_back('o');
break;
case '7':
result.push_back('p');
result.push_back('q');
result.push_back('r');
result.push_back('s');
break;
case '8':
result.push_back('t');
result.push_back('u');
result.push_back('v');
break;
case '9':
result.push_back('w');
result.push_back('x');
result.push_back('y');
result.push_back('z');
break;
}
return result;
}
void helper(string digits, string cur, int num, vector<string>& result )
{
if(num==digits.size())
{
result.push_back(cur);
}
char digit = digits[num];
vector<char> option = switchchar(digit);
for(int i=0;i<option.size();i++)
{
helper(digits, cur+option[i], num+1, result);
}
}
vector<string> letterCombinations(string digits) {
vector<string> result;
string cur = "";
helper(digits, cur, 0, result);
return result;
}
Labels:
Dynamic Programming
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment