Question 17

Letter Combinations of a Phone Number

Given a string containing digits from 2-9, return all possible letter combinations that the number could represent. Each digit corresponds to a set of letters on a traditional telephone keypad.

Approach: DFS

We can use Depth First Search (DFS) to explore all possible letter combinations by treating each digit as a level in a decision tree, where each branch corresponds to one of the letters mapped to that digit.

1. Map Digits to Letters: Define a mapping from each digit to its corresponding letters.
2. Recursive DFS: For each digit in the input, add each possible letter to a path and recursively explore the next digit. When the path reaches the same length as the input digits, add it to the result list.
3. Backtracking: Use backtracking to remove the last letter after each recursive call to explore other branches.

Java Code Implementation

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

public class PhoneNumberLetterCombinations {
    
    // Map digits to corresponding letters
    private static final Map<Character, String> phoneMap = new HashMap<>() {{
        put('2', "abc"); put('3', "def");
        put('4', "ghi"); put('5', "jkl"); put('6', "mno");
        put('7', "pqrs"); put('8', "tuv"); put('9', "wxyz");
    }};
    
    // Method to return all letter combinations
    public List<String> letterCombinations(String digits) {
        List<String> combinations = new ArrayList<>();
        
        // Edge case: empty input
        if (digits == null || digits.isEmpty()) {
            return combinations;
        }
        
        // Start DFS with an empty path
        dfs(combinations, digits, new StringBuilder(), 0);
        return combinations;
    }
    
    // DFS recursive function
    private void dfs(List<String> combinations, String digits, StringBuilder path, int index) {
        // Base case: path length matches digits length
        if (index == digits.length()) {
            combinations.add(path.toString());
            return;
        }
        
        // Get the letters that the current digit maps to
        char digit = digits.charAt(index);
        String letters = phoneMap.get(digit);
        
        // Recursive DFS on each letter
        for (char letter : letters.toCharArray()) {
            path.append(letter);          // Choose letter
            dfs(combinations, digits, path, index + 1);  // Explore
            path.deleteCharAt(path.length() - 1);        // Backtrack
        }
    }

    public static void main(String[] args) {
        PhoneNumberLetterCombinations solution = new PhoneNumberLetterCombinations();
        System.out.println(solution.letterCombinations("23")); // Example test case
    }
}

Explanation

DFS Recursive Function

The dfs function takes the current path and explores all possible branches (letters) mapped by the current digit. When index reaches digits.length(), the path is added to combinations as a complete combination.

Backtracking

After each recursive call, deleteCharAt() removes the last character from path, allowing the function to backtrack and explore other possible paths for previous digits.

Complexity Analysis

• Time Complexity: ( O(3^N \times 4^M) ), where ( N ) and ( M ) are the counts of digits that map to 3 letters (such as 2, 3, 4) and 4 letters (such as 7, 9) respectively. This reflects the total number of possible letter combinations.
• Space Complexity: ( O(3^N \times 4^M) ), for storing the resulting list of combinations.

This complexity accounts for the recursive call stack and the storage required for all potential letter combinations.