Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Leetcode #17: Letter Combinations of a Phone Number
class Solution {
public:
map<char, string> numToString = {{'2', "abc"}, {'3', "def"}, {'4', "ghi"},
{'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"},
{'8', "tuv"}, {'9', "wxyz"}};
vector<string> answer;
string input;
void recurse(string path, int index) {
if (!(index < input.length())) { // the entire string is processed already.
if (!path.empty()) { // only add non-empty strings.
answer.push_back(path); // add the current value in final answer.
}
return; // nothing else to do here.
}
char currentChar = input[index];
string possibilities = numToString[currentChar];
for (char c: possibilities) { // for each possibility.
path.push_back(c); // assume current possibility.
recurse(path, index+1); // recursively solve the remaining problem.
path.pop_back(); // undo the current possibility.
}
}
vector<string> letterCombinations(string digits) {
input = digits;
recurse("", // empty string in the beginning.
0); // what index in input to start the recursion.
return answer;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment