Letter Combinations of a Phone Number

Problem Link

Letter Combinations of a Phone Number – LeetCode

Problem: Letter Combinations of a Phone Number

Problem Statement

Given a string containing digits from 2 to 9, return all possible letter combinations that the number could represent. Return the answer in any order.

The mapping is similar to the telephone keypad:

2 -> "abc", 3 -> "def", 4 -> "ghi", 5 -> "jkl",  
6 -> "mno", 7 -> "pqrs", 8 -> "tuv", 9 -> "wxyz"

Examples

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

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

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

Constraints

• 0 <= digits.length <= 4

• digits[i] is a digit between '2' and '9'

Intuition

This is a combinatorial generation problem where for each digit, we branch into all characters it maps to.

We use Input-Output Method:

• Input: the remaining digits yet to process

• Output: the current combination built so far

For each digit, we append each of its corresponding letters to the current output and recursively process the remaining digits.

Input-Output Recursive Method

Function Signature

void helper(String ip, String op, String[] chars, List<String> ans)

Parameters

• ip: input digits left to process

• op: output string built so far

• chars: digit-to-letter mapping

• ans: result list

Base Case

If ip.length() == 0 and op.length() > 0:

• We’ve built a complete valid combination → add to result list.

Recursive Case

1. Take the first digit from ip.

2. Convert to its mapped string using chars.

3. For each character ch in mapped string:

   • Append ch to op

   • Recur with ip.substring(1)

Code (Java)

class Solution {
    public List<String> letterCombinations(String digits) {
        String[] chars = {
            "", "", "abc", "def", "ghi", 
            "jkl", "mno", "pqrs", "tuv", "wxyz"
        };
        List<String> ans = new ArrayList<>();
        helper(digits, "", chars, ans);
        return ans;
    }

    public void helper(String ip, String op, String[] chars, List<String> ans) {
        // Base Case
        if (ip.length() == 0) {
            if (!op.equals("")) {
                ans.add(op);
            }
            return;
        }

        // Get the current digit's mapped characters
        int num = Character.getNumericValue(ip.charAt(0));
        String currCh = chars[num];
        String remaining = ip.substring(1);

        // For each character mapped to the current digit, make a recursive call
        for (int i = 0; i < currCh.length(); i++) {
            helper(remaining, op + currCh.charAt(i), chars, ans);
        }
    }
}

Time and Space Complexity

• Time Complexity: O(4^n) in the worst case (when digits like 7 or 9 appear which map to 4 letters)

  • Total combinations = product of number of characters for each digit

• Space Complexity:

  • O(n) recursion depth

  • O(4^n) result list in worst case

Dry Run

Input: "23"

helper("23", "")
→ for '2' → "abc"

→ helper("3", "a")
    → for '3' → "def"
        → "ad", "ae", "af"
→ helper("3", "b")
    → "bd", "be", "bf"
→ helper("3", "c")
    → "cd", "ce", "cf"

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

Conclusion

This problem is a direct application of the Input-Output recursive method for generating combinations. It demonstrates the power of recursive tree traversal when each level branches into multiple options. It's a great way to understand recursion in combination generation.