Letter Combinations of a Phone Number | Leetcode 17 Solution

The Letter Combinations of a Phone Number problem is a classic question often asked in technical interviews. It challenges your understanding of backtracking, recursion, and efficient problem-solving. Let’s explore all possible solutions, from a naive approach to an optimized one, with their explanations, complexities, and Java implementations.

Problem Statement for Letter Combinations of a Phone Number

Given a string containing digits from 2 to 9, return all possible letter combinations that the number could represent. Each digit maps to a set of letters (like on a phone keypad). Return the combinations in any order.

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

Letter Combinations of a Phone Number

Example

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

Input: digits = ""
Output: []

Key Insights

  • Each digit maps to a group of letters, e.g., 2 -> "abc", 3 -> "def", etc.
  • The task is to generate all combinations of letters where each combination has one letter from each digit’s mapping.

Approach 1: Naive Solution Using Iterative Combination Building for Letter Combinations of a Phone Number

Explanation

This solution builds combinations iteratively by appending one letter at a time for each digit’s mapping. Although simple, it lacks elegance and efficiency for larger inputs.

Code

import java.util.*;

public class LetterCombinationsNaive {
    public static List<String> letterCombinations(String digits) {
        if (digits == null || digits.isEmpty()) return new ArrayList<>();

        String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        List<String> combinations = new ArrayList<>();
        combinations.add(""); // Start with an empty combination

        for (char digit : digits.toCharArray()) {
            List<String> temp = new ArrayList<>();
            for (String combination : combinations) {
                for (char letter : mapping[digit - '0'].toCharArray()) {
                    temp.add(combination + letter);
                }
            }
            combinations = temp;
        }
        return combinations;
    }

    public static void main(String[] args) {
        System.out.println(letterCombinations("23"));
    }
}

Complexity

  • Time Complexity: O(3n⋅4m), where nnn is the number of digits mapping to 3 letters, and mmm is the number of digits mapping to 4 letters.
  • Space Complexity: O(n⋅k) where k is the total number of combinations.

Approach 2: Recursive Backtracking solution for Letter Combinations of a Phone Number

Explanation

Backtracking is the most elegant solution. We recursively explore all paths, appending a letter for each digit at every step. If we exhaust all digits, we store the combination.

Code

import java.util.*;

public class LetterCombinationsRecursive {
    public static List<String> letterCombinations(String digits) {
        if (digits == null || digits.isEmpty()) return new ArrayList<>();
        
        String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        List<String> result = new ArrayList<>();
        backtrack(result, digits, mapping, new StringBuilder(), 0);
        return result;
    }

    private static void backtrack(List<String> result, String digits, String[] mapping, StringBuilder current, int index) {
        if (index == digits.length()) {
            result.add(current.toString());
            return;
        }

        String letters = mapping[digits.charAt(index) - '0'];
        for (char letter : letters.toCharArray()) {
            current.append(letter);
            backtrack(result, digits, mapping, current, index + 1);
            current.deleteCharAt(current.length() - 1); // Backtrack
        }
    }

    public static void main(String[] args) {
        System.out.println(letterCombinations("23"));
    }
}

Complexity

  • Time Complexity: O(3n⋅4m).
  • Space Complexity: O(n)(recursion stack depth).

Approach 3: Optimized Backtracking (Reducing Redundant Operations) for Letter Combinations of a Phone Number

Explanation

This approach is similar to the recursive one but optimizes letter traversal by reducing redundant operations or extra memory usage.

Code

import java.util.*;

public class LetterCombinationsOptimized {
    public static List<String> letterCombinations(String digits) {
        if (digits == null || digits.isEmpty()) return Collections.emptyList();

        String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        List<String> result = new ArrayList<>();
        backtrack(result, mapping, digits, 0, "");
        return result;
    }

    private static void backtrack(List<String> result, String[] mapping, String digits, int index, String path) {
        if (index == digits.length()) {
            result.add(path);
            return;
        }

        String letters = mapping[digits.charAt(index) - '0'];
        for (char letter : letters.toCharArray()) {
            backtrack(result, mapping, digits, index + 1, path + letter);
        }
    }

    public static void main(String[] args) {
        System.out.println(letterCombinations("23"));
    }
}

Complexity

  • Time Complexity: O(3n⋅4m).
  • Space Complexity: O(n).

Final Thoughts for Letter Combinations of a Phone Number

Each approach solves the problem but varies in readability, efficiency, and scalability:

ApproachComplexitySuitability
Iterative CombinationHighSimple but not recommended for large inputs.
Recursive BacktrackingModerateBest for clarity and moderate input sizes.
Optimized BacktrackingModerateMore memory-efficient for practical applications.

The backtracking approach is widely preferred for its clarity and efficiency. Depending on the constraints, you can use the naive or optimized version.

Leave a comment