Introduction
In this blog post, we'll delve into a problem that involves translating numeric digits into their corresponding letter combinations, much like the letters associated with the buttons on a telephone keypad. We'll examine both a naive approach and an optimized solution to generate all possible letter combinations for a given input.
Problem Statement
Given a string containing digits from 2 to 9 inclusive, we are tasked with returning all possible letter combinations that these numbers could represent. Each digit maps to a set of letters, similar to the arrangement on telephone buttons. For instance, the digit '2' corresponds to 'abc', '3' to 'def', and so forth. The goal is to generate all combinations of these letters for a given input string of digits.
Example 1
Input: "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2
Input: ""
Output: []
Example 3
Input: "2"
Output: ["a","b","c"]
Naive Approach
One straightforward approach to solving this problem is to use recursive backtracking. The idea is to explore all possible combinations by considering each digit and its associated letters. We'll build the combinations recursively, and if a combination is valid (i.e., of the same length as the input digits), we add it to the result.
Naive Approach Code
cpp
#include <vector>
#include <string>
class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string> result;
if (digits.empty()) {
return result;
}
vector<string> phoneMap = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
string currentCombination;
backtrack(digits, 0, phoneMap, currentCombination, result);
return result;
}
private:
void backtrack(const string& digits, int index, const vector<string>& phoneMap, string& currentCombination, vector<string>& result) {
if (index == digits.size()) {
result.push_back(currentCombination);
return;
}
string letters = phoneMap[digits[index] - '0'];
for (char letter : letters) {
currentCombination.push_back(letter);
backtrack(digits, index + 1, phoneMap, currentCombination, result);
currentCombination.pop_back();
}
}
};
Naive Approach Explanation
1. The `letterCombinations` function initializes the result vector and checks if the input string `digits` is empty. If it is, an empty result vector is returned.
2. The `phoneMap` vector is used to map each digit to its corresponding letters.
3. The `backtrack` function is a recursive helper function. It takes the current index, the phone map, the current combination being built, and the result vector.
4. In the `backtrack` function, the base case checks if the current combination is of the same length as the input digits. If it is, the current combination is added to the result vector.
5. The function then retrieves the letters corresponding to the current digit and iterates over them. For each letter, it appends it to the current combination, makes a recursive call to explore further possibilities, and then unchooses the letter (backtracks) to try the next one.
6. Finally, the `letterCombinations` function returns the result vector containing all possible letter combinations.
Optimized Approach
While the naive approach works, it can be optimized by using a queue-based approach. This involves iteratively building combinations by dequeuing and appending letters to the existing combinations in the queue.
Optimized Approach Code
cpp
#include <vector>
#include <string>
#include <queue>
class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string> result;
if (digits.empty()) {
return result;
}
vector<string> phoneMap = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
queue<string> combinations;
combinations.push("");
for (char digit : digits) {
int size = combinations.size();
for (int i = 0; i < size; ++i) {
string currentCombination = combinations.front();
combinations.pop();
for (char letter : phoneMap[digit - '0']) {
combinations.push(currentCombination + letter);
}
}
}
while (!combinations.empty()) {
result.push_back(combinations.front());
combinations.pop();
}
return result;
}
};
Optimized Approach Explanation
1. The `letterCombinations` function initializes the result vector and checks if the input string `digits` is empty. If it is, an empty result vector is returned.
2. The `phoneMap` vector is used to map each digit to its corresponding letters.
3. A queue, `combinations`, is initialized with an empty string as the starting point.
4. Iterate over each digit in the input string. For each digit, dequeue the current combination from the front of the queue and enqueue new combinations by appending each letter corresponding to the digit.
5. Repeat this process for all digits, and the queue will contain all possible combinations.
6. Transfer the combinations from the queue to the result vector.
Conclusion
In this blog post, we explored a problem that involves generating all possible letter combinations for a given string of digits. We discussed both a naive backtracking approach and an optimized queue-based approach, providing code implementations and explanations for each. The optimized approach is more efficient and avoids the overhead of recursive calls. Depending on the specific requirements and constraints, either approach can be used to solve the problem effectively.
