17. Letter Combinations of a Phone Number

[mah-shamim]

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

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

Example 1:

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

Example 2:

• Input: digits = ""
• Output: []

Example 3:

• Input: digits = "2"
• Output: ["a","b","c"]

Constraints:

• 0 <= digits.length <= 4
• digits[i] is a digit in the range ['2', '9'].

[mah-shamim]

To solve this problem, we can follow these steps:

1. Mapping Creation:
   Create an associative array to map each digit to its corresponding letters.

2. Recursive Function:
   Use a recursive function to build combinations. This function will take the current combination being built and the remaining digits to process.

3. Base Case:
   When no more digits are left, add the current combination to the result list.

4. Recursive Case:
   For each letter mapped from the current digit, append it to the current combination and recurse with the remaining digits.

Let's implement this solution in PHP: 17. Letter Combinations of a Phone Number

<?php
    /**
     * @param String $digits
     * @return String[]
     */
    function letterCombinations($digits) {
               if (empty($digits)) {
            return [];
        }
        $letters = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
        $ans = [];
        $curr = '';
        $this->findCombinations(0, $digits, $letters, $curr, $ans);
        return $ans;
    }

    private function findCombinations($start, $nums, $letters, &$curr, &$ans) {
        if (strlen($curr) == strlen($nums)) {
            $ans[] = $curr;
            return;
        }
        for ($i = $start; $i < strlen($nums); $i++) {
            $n = intval($nums[$i]);
            for ($j = 0; $j < strlen($letters[$n]); $j++) {
                $ch = $letters[$n][$j];
                $curr .= $ch;
                $this->findCombinations($i + 1, $nums, $letters, $curr, $ans);
                $curr = substr($curr, 0, -1);
            }
        }
    }

// Test the function
print_r(letterCombinations("23")); // Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
print_r(letterCombinations("")); // Output: []
print_r(letterCombinations("2")); // Output: ["a","b","c"]
?>

Explanation:

1. Mapping Creation: An associative array $phoneMap maps digits to their corresponding letters.

2. Recursive Function: The backtrack function builds combinations by appending letters and processing the remaining digits.

3. Base Case: When no digits are left (strlen($nextDigits) === 0), the current combination is added to the result.

4. Recursive Case: For each letter corresponding to the current digit, the function recursively builds the combination.

This approach is efficient given the constraints and handles edge cases like empty input properly. If you have any more questions or need further modifications, let me know!