Letter Combinations of a Phone Number

Q: Какова временная сложность задачи «Комбинации букв телефонного номера»?

Это O(4^n · n) для n цифр: строк может быть 4^n, если каждая цифра — 7 или 9, и на запись каждой требуется n шагов. Если клавиши содержат только по три буквы, сложность составляет O(3^n · n) . Ни одно решение не может работать быстрее, поскольку таков размер выходных данных. Для возврата с возвратом требуется O(n) дополнительной памяти помимо выходных данных.

СреднеПоиск с возвратом

+10

На телефонной клавиатуре каждой цифре от 2 до 9 соответствуют несколько букв: 2 — abc, 3 — def, 4 — ghi, 5 — jkl, 6 — mno, 7 — pqrs, 8 — tuv, а 9 — wxyz.

Дана строка digits. Выбери по одной букве для каждой цифры, сохраняя порядок цифр, и получишь строку, которую можно набрать этими клавишами. Верни все такие строки, отсортированные в лексикографическом порядке (как в словаре). Для "23" это девять строк — от "ad" до "cf".

Функция

letterCombinations(digits: string) → string-array

digitsstring: нажатые цифры, каждая от 2 до 9
Возвращаетstring-array: все строки, которые могут вводить клавиши, в лексикографическом порядке

Ограничения

1 ≤ digits.length ≤ 4
Каждый символ в digits — это цифра от 2 до 9.
Ответ содержит не более 4⁴ = 256 строк.

Примеры

Ввод: digits = "23"
Вывод: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
Пояснение: 2 предлагает a, b, c, а 3 предлагает d, e, f. Каждая первая буква сочетается с каждой второй, поэтому получается 3 × 3 = 9 строк, и если перечислять их так, чтобы первая буква менялась медленнее всего, они останутся отсортированными.

Ввод: digits = "94"
Вывод: ["wg", "wh", "wi", "xg", "xh", "xi", "yg", "yh", "yi", "zg", "zh", "zi"]
Пояснение: В слове 9 четыре буквы, а в слове 4 — три, поэтому существует 4 × 3 = 12 строк. Все три строки, начинающиеся с w, идут перед первой строкой, начинающейся с x.

+14 скрытых тестов при отправке

Дополнительный вопрос

Предположим, вам нужны только сочетания, которые являются настоящими словами из словаря. Как избежать предварительного создания всех 4^n строк?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Здесь нельзя ничего пропустить: сам ответ содержит до 4^n строк, поэтому любое правильное решение тратит как минимум столько же усилий на их запись. Задача проверяет, умеешь ли ты систематически генерировать набор вариантов, не пропуская и не повторяя ни одного. Это простейшая форма поиска с возвратом: дерево решений с одним уровнем на каждую цифру, которое обходится в глубину, где каждый лист — это ответ.

Собирайте строки по одной цифре за раз

Идея

Составляйте ответы по одной цифре за раз. Начните со списка, в котором находится одна пустая строка. Для "23" цифра 2 превращает её в a, b, c. Затем цифра 3 дополняет каждую из этих трёх буквами d, e и f, в результате чего получаются девять строк длины 2. После последней цифры в списке будут все ответы.

Порядок получается отсортированным автоматически. Предположим, что перед обработкой цифры список отсортирован. Вы продолжаете префиксы в том же порядке, а каждый префикс — буквами клавиши слева направо. Строка с более ранним префиксом по-прежнему будет идти первой, а строки с одинаковым префиксом будут упорядочены по новой букве, то есть в алфавитном порядке.

Затраты определяются размером ответа. Для n цифр в последнем списке будет до 4^n строк длины n, а во всех предыдущих списках вместе будет не более чем вдвое меньше строк, и все они будут короче. Недостаток — расход памяти: пока вы строите очередной уровень, весь предыдущий уровень тоже остаётся в памяти, включая каждый короткий префикс, от которого вы откажетесь.

Алгоритм

Начни с combos = [""] — одного пустого префикса.
Для каждой цифры создай новый список: для каждого префикса в combos и каждой буквы на клавише этой цифры добавь prefix + letter.
Замени combos новым списком.
После последней цифры верни combos.

KEYPAD = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
          "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}


def letterCombinations(digits):
    combos = [""]  # every prefix built so far; one empty prefix to start
    for digit in digits:
        # Each old prefix grows by each letter of this digit, in order.
        combos = [prefix + letter for prefix in combos for letter in KEYPAD[digit]]
    return combos

Поиск с возвратом по дереву решений

Идея

Представь ответ в виде дерева решений. Корень — пустая строка. Для "23" у него три дочерних узла: a, b и c, по одному для каждой буквы цифры 2. У каждого из них тоже по три дочерних узла — по одному для каждой буквы цифры 3. На каждом уровне дерева находится одна цифра, а девять листьев, от ad до cf, — это и есть все ответы.

Алгоритм с возвратом обходит это дерево в глубину, используя один буфер — path. На уровне i ты выбираешь букву из digits[i], добавляя её, исследуешь всё поддерево ниже, рекурсивно вызывая функцию для i+1, а затем отменяешь выбор, удаляя букву. Именно отмена выбора позволяет использовать один буфер для всего дерева: после сохранения ad, ae и af удаление последней буквы возвращает path к a, а затем к пустой строке, готовой для b. Когда i равен длине digits, буфер содержит полный ответ, и ты сохраняешь его копию.

Если на каждом уровне пробовать буквы слева направо, листья посещаются в словарном порядке, поэтому сортировать результат не нужно. В этой задаче каждая ветвь заканчивается ответом, поэтому отсекать нечего; глубина дерева составляет всего 4 уровня, а количество листьев не превышает 256. Для записи ответов по-прежнему требуется O(4^n · n) операций, но дополнительная память — буфер и стек вызовов — составляет O(n), а не целый уровень префиксов. Тот же цикл «выбрать, исследовать, отменить выбор» решает задачи на подмножества, перестановки, сумму комбинаций и поиск слова.

Алгоритм

Оставь пустыми path и result.
Определи backtrack(i): если i равен длине digits, сохрани копию path и вернись.
Иначе для каждой буквы на клавише digits[i], по порядку: добавь её в path, вызови backtrack(i+1), затем удали её.
Вызови backtrack(0) и верни result.

KEYPAD = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
          "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}


def letterCombinations(digits):
    result = []
    path = []  # the letters chosen so far, one per digit

    def backtrack(i):
        if i == len(digits):
            # Every digit has a letter: this leaf is one finished string.
            result.append("".join(path))
            return
        for letter in KEYPAD[digits[i]]:
            path.append(letter)   # choose
            backtrack(i + 1)      # explore the digits after this one
            path.pop()            # undo, so the next letter can take its place

    backtrack(0)
    return result

Ловушки и крайние случаи

Сам поиск короткий, поэтому большинство ошибок связано с клавиатурой или общим буфером.

Предполагать, что у каждой клавиши по три буквы. На клавише 7 — pqrs, а на клавише 9 — wxyz, поэтому, если брать три буквы с индекса (d-2)*3 алфавита, буква s пропускается для 7, а для 8 последовательность начинается с s вместо t. Запиши клавиатуру в виде таблицы.
Забыть откат. Если не удалить букву после рекурсивного вызова, path продолжит расти, и второй ответ для "23" будет ade вместо ae.
Сохранить буфер вместо его копии. В Python вызов result.append(path) сохранит один и тот же список девять раз, и к концу он будет пустым. При сохранении объединяй его в новую строку.
Нарушить порядок. Если перебирать буквы клавиши справа налево или наращивать строки из стека в итеративной версии, ответы будут в порядке, отличном от отсортированного, которого требует задача.
Воспринимать строку цифр как число. В языках со слабой типизацией, таких как PHP и R, значение "23" может прийти к тебе как число 23. Преобразуй его в текст, прежде чем обращаться к его символам по индексу.

Частые вопросы4

Какова временная сложность задачи «Комбинации букв телефонного номера»?

Это O(4^n · n) для n цифр: строк может быть 4^n, если каждая цифра — 7 или 9, и на запись каждой требуется n шагов. Если клавиши содержат только по три буквы, сложность составляет O(3^n · n). Ни одно решение не может работать быстрее, поскольку таков размер выходных данных. Для возврата с возвратом требуется O(n) дополнительной памяти помимо выходных данных.

Сможешь решить задачу «Комбинации букв» без рекурсии?

Да. Стройте варианты ответов уровень за уровнем: начните с одной пустой строки и для каждой цифры дополняйте каждую имеющуюся строку каждой буквой с этой клавиши. Это требует столько же работы и представляет собой то же дерево, которое обходят в ширину, а не в глубину. В памяти хранится целый уровень префиксов, тогда как при рекурсии нужен только стек глубиной, равной количеству цифр.

Почему при возврате с возвратом комбинации возвращаются в отсортированном порядке?

Все ответы имеют одинаковую длину, и при обходе в глубину завершается перебор каждой строки, начинающейся с a, прежде чем на первом уровне будет выбрана b. То же самое происходит на каждом уровне, если буквы каждого ключа проверяются слева направо. Это и есть словарный порядок, поэтому сортировка не нужна.

А как насчёт цифр 0 и 1?

На клавиатуре телефона с цифрами 0 и 1 не связано ни одной буквы, а в этой версии задачи используются только цифры от 2 до 9. Если бы они могли встречаться, пришлось бы решить, нужно ли пропускать такую цифру или считать ответ пустым, поскольку она не предлагает букв на выбор. На собеседовании уточни, какой вариант нужен, прежде чем писать код.

Python

def letterCombinations(digits):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

digits = "23"

Ожидается

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