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"].
class Solution {
public:
vector<string> v = {"","","abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
vector<string> ans;
char str[1000];
//string tmp;
void DFS(int cur,string &d)
{
if(cur == d.size())
{
str[d.size()] = '\0';
string tmp = str;
ans.push_back(tmp);
return;
}
int index = d[cur] - '0';
for(int i=0;i<v[index].size();i++)
{
str[cur] = v[index][i];
// cout<<tmp[cur]<<endl;
DFS(cur+1,d);
}
}
vector<string> letterCombinations(string digits) {
if(digits.size()<=0)
return ans;
ans.clear();
DFS(0,digits);
return ans;
}
};
