Introduce

Problem Analysis (Using “258” as example)

//2   a    b    c
//5   j    k    l
//8   t    u    v

Possible letter combinations:

• a, j, t (no further options, this is one combination)
• a, j, u (no further options, another combination)
• a, j, v (another combination)
• a, k, t (another combination)

this resembles a depth-first search (DFS) traversal of an n-ary tree.

Solution Approach

To traverse all combinations starting with ‘a’, we need to traverse all subtrees rooted at ‘j’, ‘k’, and ‘l’ (the next level letters for digit ‘5’)

Similarly, to traverse combinations starting with ‘j’, we need to traverse subtrees rooted at ‘t’, ‘u’, and ‘v’ (the next level letter for digit ‘8’)

Recursive implementation

class Solution {
public:vector<string> letterCombinations(string digits) {}
};

We`ll implement a recursive solution:

class Solution {
public:void _letterCombinations(string digits){}vector<string> letterCombinations(string digits) {}
};

Digit-to-Letter Mapping

Since we`re dealing with digit 2-9, we can store the corresponding letters in an string array for O(1) lookup:

class Solution {string tele[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; 
public:void _letterCombinations(string digits){}vector<string> letterCombinations(string digits) {}
};

Tree Traversal Implementation

Now we implement the traversal starting from digits[0]:

class Solution {string tele[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; 
public:// Traverse all subtrees at level ivoid _letterCombinations(string digits, int i){// Get corresponding lettersstring str = tele[digits[i] - '0'];for (int j = 0; j < str.size(); j++) {// Traverse next level_letterCombinations(digits, i + 1);}}vector<string> letterCombinations(string digits) {// Start traversal from level 0_letterCombinations(digits, 0);}
};

Adding Recursion Boundary Condition

we must add a termination condition for the recursion:

class Solution {string tele[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; 
public:// Traverse all subtrees at level ivoid _letterCombinations(string digits, int i){// Recursion boundaryif (i == digits.size()) {return;}// Get corresponding lettersstring str = tele[digits[i] - '0'];for (int j = 0; j < str.size(); j++) {// Traverse next level_letterCombinations(digits, i + 1);}}vector<string> letterCombinations(string digits) {// Start traversal from level 0_letterCombinations(digits, 0);}
};

Storing Results

We need to store the combinations in a vector:

class Solution {string tele[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; 
public:// Traverse all subtrees at level ivoid _letterCombinations(string digits, int i, vector<string>& ret){// Recursion boundaryif (i == digits.size()) {return;}// Get corresponding lettersstring str = tele[digits[i] - '0'];for (int j = 0; j < str.size(); j++) {// Traverse next level_letterCombinations(digits, i + 1, ret);}}vector<string> letterCombinations(string digits) {vector<string> result;// Start traversal from level 0_letterCombinations(digits, 0, result);return result; // Don't forget to return!}
};

Building Combinations

We need to build the combinations by passing the current combination down the recursion:

class Solution {string tele[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; 
public:// Traverse all subtrees at level ivoid _letterCombinations(string digits, int i, string current, vector<string>& ret){// Recursion boundaryif (i == digits.size()) {ret.push_back(current);return;}// Get corresponding lettersstring str = tele[digits[i] - '0'];for (int j = 0; j < str.size(); j++) {// Traverse next level with updated combination_letterCombinations(digits, i + 1, current + str[j], ret);}}vector<string> letterCombinations(string digits) {vector<string> result;string current;// Start traversal from level 0_letterCombinations(digits, 0, current, result);return result;}
};

Edge Case Handling

Finally, we handle the empty input case:

class Solution {string tele[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; 
public:// Traverse all subtrees at level ivoid _letterCombinations(string digits, int i, string current, vector<string>& ret){// Recursion boundaryif (i == digits.size()) {ret.push_back(current);return;}// Get corresponding lettersstring str = tele[digits[i] - '0'];for (int j = 0; j < str.size(); j++) {// Traverse next level with updated combination_letterCombinations(digits, i + 1, current + str[j], ret);}}vector<string> letterCombinations(string digits) {vector<string> result;if (digits.empty()) {return result;}string current;// Start traversal from level 0_letterCombinations(digits, 0, current, result);return result;}
};