LetterCombinationsOfPhoneNumber.java

package com.thealgorithms.strings;

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

public final class LetterCombinationsOfPhoneNumber {

 private static final char EMPTY = '\0';

 // Mapping of numbers to corresponding letters on a phone keypad
 private static final String[] KEYPAD = new String[] {" ", String.valueOf(EMPTY), "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

 private LetterCombinationsOfPhoneNumber() {
 }

 /**
 * Generates a list of all possible letter combinations that the provided
 * array of numbers could represent on a phone keypad.
 *
 * @param numbers an array of integers representing the phone numbers
 * @return a list of possible letter combinations
 */
 public static List<String> getCombinations(int[] numbers) {
 if (numbers == null) {
 return List.of("");
 }
 return generateCombinations(numbers, 0, new StringBuilder());
 }

 /**
 * Recursive method to generate combinations of letters from the phone keypad.
 *
 * @param numbers the input array of phone numbers
 * @param index the current index in the numbers array being processed
 * @param current a StringBuilder holding the current combination of letters
 * @return a list of letter combinations formed from the given numbers
 */
 private static List<String> generateCombinations(int[] numbers, int index, StringBuilder current) {
 // Base case: if we've processed all numbers, return the current combination
 if (index == numbers.length) {
 return new ArrayList<>(Collections.singletonList(current.toString()));
 }

 final var number = numbers[index];
 if (number < 0 || number > 9) {
 throw new IllegalArgumentException("Input numbers must in the range [0, 9]");
 }

 List<String> combinations = new ArrayList<>();

 // Iterate over each letter and recurse to generate further combinations
 for (char letter : KEYPAD[number].toCharArray()) {
 if (letter != EMPTY) {
 current.append(letter);
 }
 combinations.addAll(generateCombinations(numbers, index + 1, current));
 if (letter != EMPTY) {
 current.deleteCharAt(current.length() - 1); // Backtrack by removing the last appended letter
 }
 }

 return combinations;
 }
}