Letter Combinations of a Phone Number - LeetCode Solution in Java

1. Introduction

The "Letter Combinations of a Phone Number" problem involves generating all possible letter combinations that can be formed from a string of digits on a telephone keypad.

2. Problem

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

3. Solution Steps

1. Map each digit to its corresponding letters.

2. Use a recursive approach to build combinations.

3. If the current combination length matches the input digits length, add it to the result.

4. Iterate through the letters for the current digit and recurse for the next digit.

4. Solution in Java - Recursive Approach

public List<String> letterCombinations(String digits) {
    List<String> result = new ArrayList<>();
    // Return empty list if input is empty
    if (digits == null || digits.isEmpty()) {
        return result;
    }
    // Mapping of digits to corresponding letters
    String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    // Start recursive function
    letterCombinationsRecursive(result, digits, "", 0, mapping);
    return result;
}

private void letterCombinationsRecursive(List<String> result, String digits, String current, int index, String[] mapping) {
    // If the current string length is equal to digits length, add to result
    if (index == digits.length()) {
        result.add(current);
        return;
    }
    // Get letters that the current digit maps to
    String letters = mapping[digits.charAt(index) - '0'];
    // Loop through these letters
    for (int i = 0; i < letters.length(); i++) {
        // Call the function recursively with next digit
        letterCombinationsRecursive(result, digits, current + letters.charAt(i), index + 1, mapping);
    }
}

This solution uses recursive backtracking to build and explore all possible combinations of letters for the given digits, adhering to the mapping provided by the telephone keypad.

Explanation:

1. The mapping array associates each digit with its corresponding letters.

2. letterCombinationsRecursive is a recursive method that builds combinations.

3. It checks if the current string length matches the digits length and adds it to the result if it does.

4. It iterates through the letters for each digit and calls itself recursively to explore further combinations.

5. This process continues until all combinations for the given digits are explored and added to the result list.

5. Solution in Java - Iterative Approach 

Solution Steps

1. Create a mapping of digits to their corresponding letters.

2. Initialize a list to store the current combinations.

3. Iterate over each digit in the input.

4. For each digit, iterate over each letter it represents and combine it with the existing combinations.

5. Update the list with new combinations for each digit.

6. Return the final list of combinations.

Solution in Java

public List<String> letterCombinations(String digits) {
    LinkedList<String> result = new LinkedList<>();
    if (digits.isEmpty()) return result;

    // Mapping of digits to corresponding letters
    String[] mapping = new String[]{"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    result.add("");

    for (int i = 0; i < digits.length(); i++) {
        int index = digits.charAt(i) - '0';
        while (result.peek().length() == i) {
            String permutation = result.remove();
            for (char c : mapping[index].toCharArray()) {
                result.add(permutation + c);
            }
        }
    }
    return result;
}

This solution uses an iterative approach with a queue (LinkedList<String>) to build up combinations level by level, corresponding to each digit in the input string.

Explanation:

1. The mapping array associates each digit with its corresponding letters.

2. LinkedList<String> result stores the current combinations.

3. Iterate over each digit, using digits.charAt(i) - '0' to get the corresponding index in the mapping.

4. For each letter that the current digit maps to, new combinations are formed by appending these letters to existing combinations.

5. The while loop ensures that combinations of the current length are processed before moving to the next digit.

6. Finally, result contains all the possible letter combinations for the given digit string.