Given a digit string, 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.
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.
思路：这也是一道DFS题。可用一个dict数组，key表示数字，value表示数字所代表的字符串。然后对数字字符串搜索。代码如下：
class Solution {
private:
vector<string> dict;
vector<string> res;
string perRes;
public:
void letterCombinationsHelper(int pos, int n, int left, string digits)
{
if (pos == n)
{
res.push_back(perRes);
}
else
{
int i,j;
for(i=0; i<n; ++i)
{
if(i>left)
{
for(j=0; j<dict[digits[i]-'0'].length(); j++)
{
perRes[pos] = dict[digits[i]-'0'][j];
letterCombinationsHelper(pos+1,n,i,digits);
}
}
}
}
}
vector<string> letterCombinations(string digits) {
dict.resize(10);
res.clear();
int i;
dict[0] = "";
dict[1] = "";
for(i=2; i<=6; ++i)
{
dict[i] = "";
dict[i] += 'a' + (i-2)*3;
dict[i] += 'a' + (i-2)*3 + 1;
dict[i] += 'a' + (i-2)*3 + 2;
}
dict[7] = "pqrs";
dict[8] = "tuv";
dict[9] = "wxyz";
int digit[10];
memset(digit, 0, sizeof(digit));
if (digits.empty())
{
res.push_back("");
return res;
}
int len = digits.length();
perRes.clear();
perRes.resize(len);
letterCombinationsHelper(0, len, -1, digits);
return res;
}
};