1.4) Letter Combinations of a Phone Number

Given a string containing digits from 2 to 9 inclusive, return all possible letter combinations that the number could represent on a telephone keypad. The mapping of digits to letters is the same as that commonly found in a telephone keypad (e.g., 2 is associated with ‘abc’, 3 is associated with ‘def’, etc.).

Sample Input/Output:

Let’s consider a sample input:

digits = "23"

Expected Output:

["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

Explanation:
For the given input "23", the digit ‘2’ is associated with ‘abc’, and the digit ‘3’ is associated with ‘def’. The possible letter combinations are ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Time and Space Complexity:

The time complexity of the solution will be O(4^N), where N is the number of digits in the input string digits. For each digit, there are up to 4 possible letters (except for ‘7’ and ‘9’, which have 4 letters each). So, the total number of combinations will be 4^N.

The space complexity will be O(N) to store the output vector and the current combination.

Now, let’s implement the solution in C++:

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

vector<string> letterCombinations(string digits) {
    vector<string> result;
    if (digits.empty()) return result;

    // Define the mapping of digits to letters on the telephone keypad
    unordered_map<char, string> phoneMap{
        {'2', "abc"}, {'3', "def"}, {'4', "ghi"},
        {'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"},
        {'8', "tuv"}, {'9', "wxyz"}
    };

    string currentCombination;
    // Helper function to backtrack and generate letter combinations
    void backtrack(int index) {
        if (index == digits.size()) {
            result.push_back(currentCombination);
            return;
        }

        char digit = digits[index];
        string letters = phoneMap[digit];
        for (char letter : letters) {
            currentCombination.push_back(letter);
            backtrack(index + 1);
            currentCombination.pop_back();
        }
    }

    backtrack(0);

    return result;
}

int main() {
    string digits = "23";
    vector<string> result = letterCombinations(digits);

    cout << "Letter Combinations:\n";
    for (const string& combination : result) {
        cout << combination << " ";
    }
    cout << endl;

    return 0;
}

In this implementation, we use backtracking to generate all possible letter combinations. The backtrack function is a recursive function that explores all possible choices for each digit in the input digits. It uses a phoneMap to map each digit to its corresponding letters on the telephone keypad.

The main function demonstrates the usage of letterCombinations by finding all possible letter combinations for the given input digits.

The output will be:

Letter Combinations:
ad ae af bd be bf cd ce cf