01 Jan 2024•Medium•PHP

Letter Combinations of a Phone Number

List every letter string a sequence of phone keypad digits could spell.

Problem

Given a string of digits from 2 to 9, return every letter combination the digits could represent on a phone keypad, where 2 maps to abc, 3 to def, and so on.

Approach

Map each digit to its letters, then build combinations with backtracking: pick one letter for the current digit, move to the next digit, and record the string once every digit has a letter.

An iterative version works too. Start with a list holding an empty string and, for each digit, extend every existing string with each of that digit's letters.

The solution files below implement this approach.

Complexity

Time: O(4^n · n): up to four letters per digit, and each finished string takes O(n) to build.
Space: O(n) for the recursion, excluding the output.

Edge cases

An empty input returns an empty list, not a list with one empty string.
Digits 7 and 9 map to four letters, so they grow the output fastest.

Solution files

PHP•letter-combinations-of-a-phone-number/solution.php

<?php
class Solution {
    private $digitToLetters = [
        '2' => ['a', 'b', 'c'],
        '3' => ['d', 'e', 'f'],
        '4' => ['g', 'h', 'i'],
        '5' => ['j', 'k', 'l'],
        '6' => ['m', 'n', 'o'],
        '7' => ['p', 'q', 'r', 's'],
        '8' => ['t', 'u', 'v'],
        '9' => ['w', 'x', 'y', 'z'],
    ];

    function letterCombinations($digits) {
        if (empty($digits)) {
            return [];
        }

        return $this->generateCombinations($digits);
    }

    private function generateCombinations($digits) {
        if (empty($digits)) {
            return [""];
        }

        $currentDigit = $digits[0];
        $remainingDigits = substr($digits, 1);
        $currentLetters = $this->digitToLetters[$currentDigit];
        $combinationsForRemaining = $this->generateCombinations($remainingDigits);

        $result = [];
        foreach ($currentLetters as $letter) {
            foreach ($combinationsForRemaining as $combination) {
                $result[] = $letter . $combination;
            }
        }

        return $result;
    }
}

$solution = new Solution();
print_r($solution->letterCombinations("23"));
print_r($solution->letterCombinations(""));
print_r($solution->letterCombinations("2"));
?>