Problem Overview

When studying computer science and preparing for technical interviews, solving the letter combinations of a phone number algorithmic problem is a fundamental exercise. Given a string containing digits from 2-9 inclusive, you are required to return all possible letter combinations that the number could represent. You may return the answer in any order.

This problem directly models the text messaging functionality on older cellular phones, where each numeric key maps to three or four letters. Understanding how to traverse these mappings helps software engineers develop robust problem-solving skills, particularly with depth-first search and recursive tree generation techniques. A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Understanding the Examples

Let us examine a few sample inputs and outputs to clarify the exact behavior expected from our algorithm.

Example 1

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

In this example, the digit '2' maps to 'a', 'b', and 'c'. The digit '3' maps to 'd', 'e', and 'f'. By generating the Cartesian product of these sets, we produce nine unique combinations.

Example 2

Input: digits = ""
Output: []

If the input string is empty, our algorithm must return an empty list immediately without entering the recursive logic.

Example 3

Input: digits = "2"
Output: ["a","b","c"]

For a single digit, the output consists of the letters corresponding to that digit as standalone strings.

Java Solution: Recursive Backtracking

Our Java implementation utilizes a straightforward backtracking strategy. We maintain a mapping from digits to their respective letters and build our combinations recursively. As we iterate through the letters for a specific digit, we append the letter to our path and recurse on the next digit. Once the path length equals the input length, we add the completed string to our results list.

class Solution {
     public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return new ArrayList<>();
        }
        Map<Character, String> digitToLetters = new HashMap<>();
        digitToLetters.put('2', "abc");
        digitToLetters.put('3', "def");
        digitToLetters.put('4', "ghi");
        digitToLetters.put('5', "jkl");
        digitToLetters.put('6', "mno");
        digitToLetters.put('7', "pqrs");
        digitToLetters.put('8', "tuv");
        digitToLetters.put('9', "wxyz");

        List<String> result = new ArrayList<>();
        backtrack(digits, 0, new StringBuilder(), result, digitToLetters);
        return result;
    }

    private void backtrack(String digits, int index, StringBuilder path, List<String> result, Map<Character, String> digitToLetters) {
        if (index == digits.length()) {
            result.add(path.toString());
            return;
        }

        char digit = digits.charAt(index);
        String letters = digitToLetters.get(digit);
        for (char letter : letters.toCharArray()) {
            path.append(letter);
            backtrack(digits, index + 1, path, result, digitToLetters);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

C++ Solution: Utilizing Vectors and Strings

The C++ solution mirrors the logical structure of the Java version but leverages the Standard Template Library (STL). We use a std::vector to store our results and an unordered_map to associate digits with their corresponding character sequences. The push_back and pop_back methods on the string object allow for efficient backtracking without incurring excessive memory allocations.

//
// Created by robert on 12/20/24.
//
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;
void backtrack(string & digits, const int index, string & current, vector<string> & result, const unordered_map<char,string> & map) {
  if (digits.length() == index) {
    result.push_back(current);
    return;
  }
   char digit = digits[index];
   string letters = map.find(digit)->second;
   for( char letter : letters ) {
        current.push_back(letter);
        backtrack( digits, index+1, current, result, map );
        current.pop_back();
   }

}
vector<string> letterCombinations(string digits) {
    vector<string> result;
    string current;

    if (digits.empty()) return result;

    unordered_map<char, string> map;

    map.insert(make_pair('2', "abc"));
    map.insert(make_pair('3', "def"));
    map.insert(make_pair('4', "ghi"));
    map.insert(make_pair('5', "jkl"));
    map.insert(make_pair('6', "mno"));
    map.insert(make_pair('7', "pqrs"));
    map.insert(make_pair('8', "tuv"));
    map.insert(make_pair('9', "wxyz"));


    backtrack(digits, 0, current,  result, map);
    return result;

}

int main(){
    vector<string> result = letterCombinations("23");
    for (const auto & i : result) {
      cout << i << endl;
    }
}

Algorithmic Complexity and Optimization

When analyzing the performance of the letter combinations of a phone number challenge, we must consider both time and space constraints. The time complexity is bounded by O(4^N * N), where N is the length of the input string. The base of the exponent is 4 because the digits '7' and '9' map to four letters. The multiplication by N accounts for the cost of building the final string when the base case is reached. From a space complexity perspective, the recursion stack and the output list will require O(4^N * N) memory.

Frequently Asked Questions

What is the time complexity of the letter combinations of a phone number problem?

The time complexity is O(4^N * N), where N is the length of the digits string. In the worst case (using digits 7 or 9), each digit can represent 4 letters, resulting in 4^N combinations, and building each string takes O(N) time.

Why is backtracking used for the letter combinations problem?

Backtracking is an effective algorithmic technique for this problem because it systematically explores all possible letter combinations by building candidates recursively and abandoning paths once they are fully explored, ensuring every valid sequence is generated.