Letter Combinations of a Phone Number - Java Solution

1. Introduction

This blog post discusses a fascinating problem often encountered in the realm of combinatorics and recursive programming: generating all possible letter combinations from a phone number. This problem is akin to the letter mappings found on a traditional telephone keypad, where each number corresponds to a set of letters.

Problem

Given a string containing digits from 2-9 inclusive, the task is to return all possible letter combinations that these numbers could represent. This requires us to consider the mapping of digits to letters on a telephone keypad and generate all possible combinations.

2. Solution Steps

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

2. Use a recursive approach to explore all possible combinations of letters.

3. Start from the first digit, append each letter it represents to the combination, and recurse for the next digit.

4. Once the length of the combination equals the length of the input digits, add the combination to the result.

5. Return the list of combinations.

3. Code Program

import java.util.ArrayList;
import java.util.List;

public class LetterCombinationsPhoneNumber {
    public static void main(String[] args) {
        System.out.println(letterCombinations("23")); // Test the function
    }

    // Function to generate all letter combinations for a given phone number
    public static List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return result;
        }

        String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        letterCombinationsRecursive(result, digits, "", 0, mapping);
        return result;
    }

    // Helper function to recursively build the combinations
    private static void letterCombinationsRecursive(List<String> result, String digits, String current, int index, String[] mapping) {
        if (index == digits.length()) {
            result.add(current);
            return;
        }

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

Output:

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

Explanation:

1. letterCombinations: This function initiates the process of generating letter combinations from a string of digits.

2. It uses a mapping array where each index corresponds to the letters associated with a digit on a phone keypad.

3. The function calls letterCombinationsRecursive to build combinations recursively.

4. letterCombinationsRecursive: A helper function that appends each letter mapped to the current digit and recurses for the next digit.

5. Once the length of the current combination matches the length of the input digits, it adds the combination to the result list.

6. The function ultimately returns a list of all possible letter combinations for the given phone number.