# DFS-based Solution for the Letter Combinations of a Phone Number problem (C++)

• ``````void DFSVisit(const string &input, const string &str, size_t nextDigit, const int *maxLetters, const char **letterNumsMap, vector<string> & combinations) {
if (nextDigit >= input.size()) return;
int d = input[nextDigit]-48;
for (size_t j = 0; j < maxLetters[d]; j++) {
string newStr = str;
newStr += letterNumsMap[d][j];
if (nextDigit+1 >= input.size()) {
combinations.push_back(newStr);
} else {
DFSVisit(input,newStr,nextDigit+1,maxLetters,letterNumsMap,combinations);
}
}
return ;
}

vector<string> letterCombinations(string digits) {
vector<string> combinations;
int maxLetters[10] = {0,0,3,3,3,3,3,4,3,4};
const char *letterNumsMap[] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
string str = "";

if (digits.size() < 1) return combinations;

DFSVisit(digits, str, 0, maxLetters, letterNumsMap, combinations);

return combinations;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.