Letter Combinations of a Phone Number

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

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

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

+10

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

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

Функция

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.

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

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

Подсказки

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

Открыто 0 из 3

Решение

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

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

Идея

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

Порядок остаётся отсортированным. Если список отсортирован перед добавлением цифры, ты расширяешь префиксы в этом порядке, а каждый префикс — буквами соответствующей клавиши слева направо: более ранний префикс по-прежнему идёт первым, а одинаковые префиксы упорядочиваются по новой букве.

Объём работы равен размеру ответа, но пока ты строишь уровень, весь предыдущий уровень тоже остаётся в памяти.

Алгоритм

Начни с 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, у каждого из которых есть дочерние узлы для d, e, f.

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

Время выполнения по-прежнему составляет 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

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

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

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

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

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

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

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

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

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

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

Тест #1

Тест #2

Тест #3

Аргумент

digits = "23"

Ожидаемый вывод

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