Letter Combinations of a Phone Number medium

Problem Statement

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

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

2: abc
3: def
4: ghi
5: jkl
6: mno
7: pqrs
8: tuv
9: wxyz

Example 1

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

Example 2

Input: digits = "" Output: []

Steps

1. Handle Empty Input: If the input string digits is empty, return an empty list.
2. Mapping: Create a mapping from digits to their corresponding letters. This can be done using a HashMap or an array.
3. Backtracking: Use a backtracking algorithm to generate all possible combinations.
   • Base Case: If the current combination's length equals the length of digits, add the combination to the result list.
   • Recursive Step: For each digit in digits, iterate through its corresponding letters. Append the letter to the current combination, make a recursive call, and then backtrack by removing the letter.

Explanation

The problem is a classic example where backtracking is the most efficient and elegant solution. Backtracking allows us to explore all possible combinations systematically. We build the combinations one digit at a time. For each digit, we explore all possible letter choices, and for each choice we recursively explore the remaining digits. Once a full combination is built (matching the length of the input digits), we add it to our result. Then we backtrack, removing the last letter to try other choices.

Code (Java)

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LetterCombinations {
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return result;
        }

        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");

        backtrack(result, digitToLetters, digits, 0, new StringBuilder());
        return result;
    }

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

        char digit = digits.charAt(index);
        String letters = digitToLetters.get(digit);
        for (int i = 0; i < letters.length(); i++) {
            combination.append(letters.charAt(i));
            backtrack(result, digitToLetters, digits, index + 1, combination);
            combination.deleteCharAt(combination.length() - 1); // Backtrack
        }
    }

    public static void main(String[] args) {
        LetterCombinations solution = new LetterCombinations();
        System.out.println(solution.letterCombinations("23")); // Output: [ad, ae, af, bd, be, bf, cd, ce, cf]
        System.out.println(solution.letterCombinations("")); // Output: []
    }
}

Complexity

• Time Complexity: O(4^N * N), where N is the length of the input digits string. In the worst case, each digit can map to 4 letters. We explore all combinations, and for each combination, we need to build the string (N).
• Space Complexity: O(N) for the recursion stack and to store the intermediate combinations. The space used by the result list is also proportional to the number of combinations generated, which is O(4^N).