Letter Combinations of a Phone Number

Letter Combinations of a Phone Number | Generate All Combinations of Letters Based on Digits

• Problem Statement: Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent, following the mapping of digits to letters as seen on telephone keypads. The number 1 does not map to any letters.

- Example 1:
  Input: digits = "23" and Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

- Example 2:
  Input: digits = "" and Output: []

- Example 3:
  Input: digits = "2" and Output: ["a", "b", "c"]

C++ Implementation

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};

        string phone_map[] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        vector<string> output;
        backtrack("", digits, phone_map, output);
        return output;
    }

private:
    void backtrack(string combination, string next_digits, string phone_map[], vector<string>& output) {
        if (next_digits.empty()) {
            output.push_back(combination);
        } else {
            string letters = phone_map[next_digits[0] - '2'];
            for (char letter : letters) {
                backtrack(combination + letter, next_digits.substr(1), phone_map, output);
            }
        }
    }
};

int main() {
    Solution solution;
    string digits;

    cout << "Enter the digits: ";
    cin >> digits;

    vector<string> result = solution.letterCombinations(digits);

    cout << "All possible letter combinations are:\n";
    for (const string& combination : result) {
        cout << combination << endl;
    }

    return 0;
}

Time and Space Complexity

Time Complexity

• $O(4^n \cdot n)$ - Where $n$ is the length of the input digits. Most digits map to 3 letters, but some (0, 1, 7, 8, 9) map to 4 letters. For the worst case with all digits mapping to 4 letters, we have $4^n$ combinations, each requiring $O(n)$ time to construct.

Space Complexity

• $O(4^n \cdot n)$ - To store all possible combinations. Each combination is a string of length $n$, and there are up to $4^n$ combinations.
• $O(n)$ - For the recursion stack depth, which is at most the length of the input digits.

Explanation

This algorithm uses backtracking to generate all letter combinations. For each digit, it retrieves the corresponding letters from the phone keypad mapping and recursively builds combinations by appending each letter. The exponential time complexity arises because the number of combinations grows exponentially with the number of digits. However, the algorithm efficiently prunes the search space by only considering valid letter mappings for each digit.