Problem Statement
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
The mapping of digits to letters is the same as on a traditional telephone keypad:
2→"abc"3→"def"4→"ghi"5→"jkl"6→"mno"7→"pqrs"8→"tuv"9→“wxyz”
LeetCode
Constraints
0 <= digits.length <= 4
digits[i] is a digit in the range ['2', '9'].Examples
Example 1:
Input: digits = "23"
Output: [
"ad",
"ae",
"af",
"bd",
"be",
"bf",
"cd",
"ce",
"cf"
]
Explanation:
The digit 2 maps to "abc", and the digit 3 maps to "def". The combinations are generated by taking one letter from each set.Example 2:
Input: digits = ""
Output: []
Explanation: Since the input string is empty, there are no combinations.Example 3:
Input: digits = "2"
Output: [
"a",
"b",
"c"
]
Explanation: The digit 2 maps to "abc", so the output consists of those letters.Different Approach
1️⃣ Backtracking
Why Backtracking?
All possible | permutations | combinations | subsets
In this problem we are told to explore all possible combinations of characters by making a choice at each digit.
Try a letter → recurse → backtrack → try next letter → recurse → ...Intuition:
The problem of finding letter combinations from a phone number can be approached using backtracking. The idea is to construct all possible combinations of letters by iterating through each digit and choosing one letter at a time until all digits have been processed.
- Mapping Digits to Letters:
- Use an array or a mapping to represent the characters associated with each digit from
2to9.
- Use an array or a mapping to represent the characters associated with each digit from
- Backtracking:
- Use a recursive function to build combinations. At each step, choose one letter for the current digit and proceed to the next digit.
- If you reach the end of the digits (base case), store the combination.
Approach:
- Base Case: If the input string is empty, return an empty vector.
- Recursive Backtracking:
- Use a helper function to generate combinations.
- For each digit, iterate over the corresponding letters and recursively build the combination.
- Once a valid combination is formed, add it to the result list.
Dry Run:
Let's consider an example where digit = "23".
1 Initial Call:
- letterCombinations("23") is called.
- solve("23", "", 0, ans, mapping) is called.
2 First Level of Recursion (i = 0):
- num = 2, value = "abc".
- Loop through value:
- output = "a", call solve("23", "a", 1, ans, mapping).
- output = "b", call solve("23", "b", 1, ans, mapping).
- output = "c", call solve("23", "c", 1, ans, mapping).
3 Second Level of Recursion (i = 1):
- For each recursive call from the first level, num = 3, value = "def".
- Loop through value:
- output = "ad", solve("23", "ad", 2, ans, mapping).
- output = "ae", solve("23", "ae", 2, ans, mapping).
- output = "af", solve("23", "af", 2, ans, mapping).
- Similarly for b and c from the first level.
4 Third Level of Recursion (i = 2):
- For each recursive call from the second level, since i is now equal to digit.length(), output is added to ans.
5 Backtracking:
After each addition to ans, the function backtracks by removing the last added letter (output.pop_back()) and continues with the next letter in the loop.
Code:
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Solution {
private:
// Recursive function to generate letter combinations
void solve(string digit, string output, int i, vector<string>& ans, string mapping[]) {
// Base case: If the current index is equal to the length of the digit string
// This means we have a complete combination, so we add it to the result
if (i >= digit.length()) {
ans.push_back(output); // Store the formed combination
return; // Return to explore other combinations
}
// Convert the current digit character to its integer representation
int num = digit[i] - '0';
// Get the corresponding letters for the current digit
string value = mapping[num];
// Loop through each character in the mapped string
for (int j = 0; j < value.length(); j++) {
// Include the current character in the output combination
output.push_back(value[j]);
// Recur to the next digit
solve(digit, output, i + 1, ans, mapping);
// Backtrack: Remove the last character added to explore other combinations
output.pop_back();
}
}
public:
// Function to return all letter combinations for a given digit string
vector<string> letterCombinations(string digit) {
vector<string> ans; // Vector to store all possible combinations
// If the input string is empty, return an empty list
if (digit.length() == 0) {
return ans;
}
int i = 0; // Starting index for processing digits
string output; // To build the current letter combination
// Mapping of digits to their corresponding letters on a phone keypad
string mapping[10] = {
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz" // 9
};
// Start the recursive process to generate combinations
solve(digit, output, i, ans, mapping);
return ans; // Return the final list of combinations
}
};
// Main function to test the solution
int main() {
Solution sol;
string digits = "23"; // Example input
vector<string> result = sol.letterCombinations(digits);
// Print the result
for (const string& combination : result) {
cout << combination << " "; // Output each combination
}
cout << endl;
return 0; // Indicate successful completion
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
// This will store all the final combinations
vector<string> result;
// Recursive function to generate combinations
void backtrack(int index, string ¤tCombo, string &digits, vector<string> &keypad) {
// BASE CASE: if the current combination is complete (same length as digits)
if (index == digits.length()) {
result.push_back(currentCombo); // Save the valid combination
return;
}
// Get the current digit (e.g., '2', '3', etc.)
char digit = digits[index];
// Get the possible letters for this digit from the keypad mapping
string letters = keypad[digit - '0'];
// Try every letter that maps to the current digit
for (char letter : letters) {
currentCombo.push_back(letter); // Step 1: Choose the letter
backtrack(index + 1, currentCombo, digits, keypad); // Step 2: Recurse for next digit
currentCombo.pop_back(); // Step 3: Backtrack (undo the choice)
}
}
// Main function to call backtracking
vector<string> letterCombinations(string digits) {
// If input is empty, return empty result
if (digits.empty()) return {};
// Map each digit to corresponding letters (like phone keypad)
vector<string> keypad = {
"", // 0 → no letters
"", // 1 → no letters
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz" // 9
};
string currentCombo; // To build combinations step-by-step
backtrack(0, currentCombo, digits, keypad); // Start from index 0
return result;
}
};
// Driver code to test
int main() {
Solution solution;
string input = "23"; // You can change this input to test
vector<string> combinations = solution.letterCombinations(input);
// Print all combinations
cout << "Letter combinations for \"" << input << "\":" << endl;
for (string combo : combinations) {
cout << combo << " ";
}
cout << endl;
return 0;
}
Complexity Analysis:
- Time Complexity:
O(2^n) - Space Complexity:
O(2^n)