PHP | LeetCode

Задача: №17. Letter Combinations of a Phone Number #medium

Условие:

Учитывая строку, содержащую цифры от 2 до 9 включительно, верните все возможные комбинации букв, которые может представлять число. Верните ответ в любом порядке. Соответствие цифр буквам (как на кнопках телефона) приведено ниже. Обратите внимание, что 1 не соответствует никаким буквам.

Решение:

class Solution { 
 
    public $result = []; 
 
    /** 
     * @param String $digits 
     * @return String[] 
     */ 
    function letterCombinations($digits) { 
        if(strlen($digits) == 0) { 
            return []; 
        } 
 
        $layouts = [ 
            2 => range('a', 'c'), 
            3 => range('d', 'f'), 
            4 => range('g', 'i'), 
            5 => range('j', 'l'),  
            6 => range('m', 'o'),  
            7 => range('p', 's'), 
            8 => range('t', 'v'), 
            9 => range('w', 'z'), 
        ]; 
 
        return $this->recursive(0, $digits, $layouts); 
    } 
 
    function recursive ($index, $chars, $layouts, $combine = '') { 
        foreach($layouts[$chars[$index]] as $currentLayout) { 
            if($layouts[$chars[$index + 1]]) { 
                $this->recursive($index + 1, $chars, $layouts, $combine . $currentLayout); 
            } else { 
                $this->result[] = $combine . $currentLayout; 
            } 
        } 
 
        return $this->result; 
    } 
}

Пояснение:
1. Проверяем, является ли входная строка пустой. Если да, возвращаем пустой массив.
2. Создаем ассоциативный массив $layouts, в котором каждой цифре соответствует массив букв, которые можно набрать на телефонной клавиатуре.
3. Вызываем рекурсивную функцию recursive(), передавая ей следующие аргументы: - $index - индекс текущей цифры в входной строке;
- $chars - входная строка, состоящая из цифр; - $layouts - ассоциативный массив с соответствием цифр и букв;
- $combine - строка, представляющая текущую комбинацию букв.
4. В рекурсивной функции recursive(): - Перебираем все буквы, соответствующие текущей цифре в $layouts.
- Если есть следующая цифра в $chars, то рекурсивно вызываем recursive(), передавая новый индекс, текущую комбинацию букв и обновленные $chars и $layouts. - Если следующей цифры нет, то добавляем текущую комбинацию букв в результирующий массив $result.
- Возвращаем $result.
5. Возвращаем конечный результат из основной функции letterCombinations().
Временная сложность этого решения - O(3^N * 4^M), где N - количество цифр, которые имеют 3 соответствующие буквы, а M - количество цифр, которые имеют 4 соответствующие буквы. Это связано с тем, что для каждой цифры мы перебираем все возможные комбинации букв.
Пространственная сложность - O(3^N * 4^M), поскольку мы храним все возможные комбинации букв в результирующем массиве.

👀1

324 views13:36