class Solution {
public:
string getChar(char ch){;
switch(ch){
case '2' : return "abc";
case '3' : return "def";
case '4' : return "ghi";
case '5' : return "jkl";
case '6' : return "mno";
case '7' : return "pqrs";
case '8' : return "tuv";
case '9' : return "wxyz";
default : return "";
}
}
void search(string &digits , int index , int end , vector<string>& ans , string maybe){
if(index >= end){
ans.push_back(maybe);
return ;
}
// cout << index << endl;
string chars = getChar(digits[index]);
int len = chars.size();
for(int i = 0 ; i < len ; i++)
search(digits , index + 1 , end , ans , maybe + chars[i]);
}
vector<string> letterCombinations(string digits) {
// Note: The Solution object is instantiated only once and is reused by each test case.
vector<string> ans;
if(digits == ""){
ans.push_back("");
return ans;
}
search(digits , 0 , digits.size() , ans , "");
return ans;
}
};