Letter Combinations of a Phone Number: бэктрекинг, BFS и itertools.product

Коротко

Задача хороша как первое знакомство с перебором: в ней нет отсечений, нет дубликатов, нет условия «сумма равна target». Есть только дерево выбора в чистом виде. Если разобраться с ним здесь, шаблон дальше без изменений переносится на подмножества, перестановки и Combination Sum. Общая теория перебора с возвратом — в статье про бэктрекинг.

Условие

Дана строка digits из цифр от 2 до 9. Каждой цифре соответствуют буквы, как на кнопках старого телефона:

Нужно вернуть все строки, которые можно получить, если для каждой цифры выбрать одну из её букв. Порядок ответа не важен.

Вход:  "23"
Выход: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

Вход:  ""
Выход: []

Это задача 17 на LeetCode, уровень Medium. Ограничения крошечные: длина строки от 0 до 4. Само по себе это подсказка. Ответ растёт экспоненциально, и никто не ждёт полиномиального алгоритма. Ждут аккуратного перебора и умения объяснить, почему он не может быть быстрее.

Интуиция: вложенные циклы, которых не напишешь заранее

Если бы цифр всегда было две, решение было бы очевидным:

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


def two_digits(digits: str) -> list[str]:
    res = []
    for a in PHONE[digits[0]]:
        for b in PHONE[digits[1]]:
            res.append(a + b)
    return res

Для трёх цифр понадобятся три вложенных цикла, для четырёх — четыре. Проблема в том, что число циклов зависит от входа, а в коде его нужно зафиксировать заранее. Все три решения ниже — это разные способы написать «$n$ вложенных циклов», когда $n$ известно только во время выполнения:

• рекурсия: каждый уровень рекурсии — это один цикл;
• итерация слоями: перебираем цифры одним циклом и на каждом шаге удлиняем все уже готовые префиксы;
• декартово произведение: отдаём вложенные циклы библиотеке.

Решение 1: бэктрекинг

Представим перебор как дерево. В корне пустая строка. На глубине i мы выбираем букву для digits[i], поэтому у каждой вершины столько детей, сколько букв у этой цифры. Листья на глубине n — готовые ответы.

                 ""
         /       |       \
        a        b        c        ← буквы цифры 2
      / | \    / | \    / | \
     ad ae af bd be bf cd ce cf    ← буквы цифры 3

Обходим дерево в глубину. Текущий путь от корня храним в списке path: перед спуском добавляем букву, после возврата убираем. Отсюда и название «перебор с возвратом».

def letter_combinations(digits: str) -> list[str]:
    if not digits:
        return []
    result = []
    path = []

    def backtrack(i: int) -> None:
        if i == len(digits):
            result.append("".join(path))
            return
        for ch in PHONE[digits[i]]:
            path.append(ch)
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return result


print(letter_combinations("23"))
# ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']

Три вещи, которые стоит проговорить вслух на интервью:

1. Состояние — индекс i следующей цифры и путь path. Больше ничего не нужно: выбор буквы для одной цифры не ограничивает выбор для других.
2. Базовый случай — i == len(digits), путь полный. Склеиваем его в строку именно здесь, а не раньше.
3. Возврат — path.pop() после рекурсивного вызова. Без него путь будет только расти, и в ответе окажутся строки вида "adef...".

Можно не держать общий список, а передавать префикс строкой:

def letter_combinations_str(digits: str) -> list[str]:
    if not digits:
        return []
    result = []

    def backtrack(i: int, prefix: str) -> None:
        if i == len(digits):
            result.append(prefix)
            return
        for ch in PHONE[digits[i]]:
            backtrack(i + 1, prefix + ch)

    backtrack(0, "")
    return result

Этот вариант короче, и pop в нём не нужен: каждая ветка получает свою копию строки. Платим за это лишним копированием на каждом шаге, prefix + ch создаёт новую строку длины до $n$. При $n \le 4$ разницы не видно, но на интервью полезно показать, что вы её понимаете. Тот же выбор «общий изменяемый путь против копии на каждом шаге» встретится в любой задаче на перебор.

То же на JavaScript

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

function letterCombinations(digits) {
  if (digits.length === 0) return []
  const result = []
  const path = []

  const backtrack = (i) => {
    if (i === digits.length) {
      result.push(path.join(''))
      return
    }
    for (const ch of PHONE[digits[i]]) {
      path.push(ch)
      backtrack(i + 1)
      path.pop()
    }
  }

  backtrack(0)
  return result
}

Ключи объекта в JS всегда строки, поэтому PHONE[digits[i]] с символом '2' найдёт запись 2: 'abc'.

Решение 2: итеративно, слой за слоем

Посмотрим на то же дерево по уровням, а не по веткам. На уровне 0 одна пустая строка. Уровень k + 1 получается из уровня k: к каждому префиксу приписываем каждую букву очередной цифры. Это обход дерева в ширину, только очередь явно не нужна: весь уровень помещается в один список.

def letter_combinations_iter(digits: str) -> list[str]:
    if not digits:
        return []
    combos = [""]
    for d in digits:
        combos = [prefix + ch for prefix in combos for ch in PHONE[d]]
    return combos

Прогон на "23":

Если интервьюер просит именно BFS с очередью, вот классическая форма. Достаём префикс из начала очереди, удлиняем его на одну букву и кладём результаты в конец. Останавливаемся, когда самый короткий префикс в очереди стал полной длины. Раз все префиксы растут по очереди, в этот момент полными стали все.

from collections import deque


def letter_combinations_queue(digits: str) -> list[str]:
    if not digits:
        return []
    queue = deque([""])
    while len(queue[0]) < len(digits):
        prefix = queue.popleft()
        for ch in PHONE[digits[len(prefix)]]:
            queue.append(prefix + ch)
    return list(queue)

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

Чем итерация лучше рекурсии? Нет стека вызовов и лимита глубины. Но в этой задаче глубина не больше 4, так что это скорее вопрос вкуса. Минус в памяти: итеративное решение держит в памяти целый уровень дерева, а рекурсивное — только один путь. Пока результат всё равно возвращается целиком, на асимптотику это не влияет, подробнее ниже.

Решение 3: itertools.product

По сути, ответ — это декартово произведение строк PHONE[d] для всех цифр. В Python для этого есть готовая функция:

from itertools import product


def letter_combinations_product(digits: str) -> list[str]:
    if not digits:
        return []
    return ["".join(p) for p in product(*(PHONE[d] for d in digits))]

product("abc", "def") выдаёт кортежи ('a', 'd'), ('a', 'e'), ... в том же порядке, что и вложенные циклы, а "".join склеивает каждый кортеж в строку. Про product, permutations, combinations и остальные функции модуля есть отдельная статья про itertools.

На собеседовании это хороший второй ответ, но плохой первый. Интервьюер почти наверняка спросит: «А как это работает внутри?». После этого всё равно придётся писать бэктрекинг. Лучше показать рекурсию, а потом сказать: «В продакшене я бы взял itertools.product, он делает ровно это». Так вы покажете и понимание, и знание стандартной библиотеки.

Есть и тонкость: product() без аргументов возвращает один пустой кортеж. Поэтому без проверки if not digits функция вернёт [""] вместо []. Это та же ловушка, что и у рекурсии, о ней ниже.

Сложность: откуда 4^n

Пусть $n$ — длина digits. У цифр 7 и 9 по четыре буквы, у остальных по три. Если среди цифр $a$ трёхбуквенных и $b$ четырёхбуквенных, то строк в ответе ровно

В худшем случае все цифры четырёхбуквенные, и получается $4^n$. Для "7979" это 256 строк, для "2345" — $3^4 = 81$.

Время. Каждая строка ответа имеет длину $n$, и её нужно как минимум записать. Отсюда нижняя граница $\Omega(n \cdot 4^n)$ для худшего входа, и все три решения её достигают:

• в бэктрекинге листьев $4^n$, на каждом "".join(path) стоит $O(n)$. Внутренних вершин меньше, чем листьев: $1 + 4 + \ldots + 4^{n-1} < 4^n / 3$, так что они асимптотику не меняют;
• в итеративном варианте на последнем слое создаётся $4^n$ строк длины $n$, а все предыдущие слои вместе дают меньше;
• product делает то же самое на C, константа меньше, порядок тот же.

Итого $O(n \cdot 4^n)$. Иногда пишут $O(4^n)$, считая длину строки константой. Это не ошибка, но лучше назвать честную оценку и пояснить, откуда множитель $n$.

Память. Сам ответ занимает $O(n \cdot 4^n)$, и никуда от этого не деться. Если результат не считать, бэктрекинг тратит $O(n)$: глубина рекурсии плюс path. Итеративный вариант держит два соседних уровня, то есть те же $O(n \cdot 4^n)$. Разница становится важной, если ответ не нужно возвращать целиком, а достаточно выдавать по одной строке. Рекурсию легко превратить в генератор, и тогда память останется $O(n)$ при любом размере ответа:

def iter_combinations(digits: str):
    if not digits:
        return
    path = []

    def backtrack(i: int):
        if i == len(digits):
            yield "".join(path)
            return
        for ch in PHONE[digits[i]]:
            path.append(ch)
            yield from backtrack(i + 1)
            path.pop()

    yield from backtrack(0)


print(next(iter_combinations("23")))  # ad

itertools.product тоже ленивый, но с оговоркой: перед началом он материализует все входные последовательности. Здесь это строки по 3–4 символа, так что на практике он тоже работает за $O(n)$ памяти. Список в итеративном решении так не умеет.

Подробнее о том, как оценивать такие переборы и почему выход алгоритма входит в его сложность, — в статьях про нотацию O-большое и вопросы о сложности на собеседовании.

Типичные ошибки

Пустой вход возвращает [""]. Это самая частая ошибка, и она есть у всех трёх подходов. Рекурсия при digits == "" сразу попадает в базовый случай и добавляет пустой путь. Итеративный вариант начинает с [""] и ни разу не заходит в цикл. product() без аргументов выдаёт один пустой кортеж. С точки зрения математики это даже логично: у пустого произведения одна комбинация. Но условие требует [], поэтому проверка if not digits: return [] в начале обязательна.

Забытый path.pop(). Путь только растёт, и уже вторая строка в ответе получается длиннее, чем нужно. Если не хочется следить за pop, передавайте префикс строкой, как во втором варианте бэктрекинга.

Добавление path вместо копии. Если вместо "".join(path) написать result.append(path), в ответе окажется $4^n$ ссылок на один и тот же список, к концу обхода пустой. В этой задаче строки неизменяемы, и ошибку легко избежать. А в Subsets и Combination Sum она возникает постоянно, там нужен path[:] или list(path).

Цифры 0 и 1. В классической постановке их во входе нет. Если интервьюер добавит их со словами «у этих кнопок нет букв», уточните, что ожидается. Если просто пропускать такую цифру, достаточно PHONE.get(d, "") и фильтра пустых строк. Если же цифра без букв делает комбинацию невозможной, ответ сразу становится пустым: в произведении появляется множитель 0. Сам вопрос «как вы обработаете некорректный ввод» — хороший повод показать, что вы думаете о крайних случаях.

Попытка «оптимизировать». Иногда кандидат пытается ускорить решение мемоизацией по суффиксу digits[i:]. Это не помогает: ответ всё равно нужно выписать целиком, а это уже $n \cdot 4^n$ работы. Мемоизация полезна, когда подзадачи повторяются, а результат у них маленький. Здесь подзадача «все хвосты для digits[i:]» действительно повторяется, но её результат огромен: приписать к каждому из закешированных хвостов букву стоит столько же, сколько эти хвосты построить.

Как это спрашивают на собеседовании

Сама задача обычно идёт разминкой на 10–15 минут. Её ценность для интервьюера в продолжениях:

• «Какая сложность и почему её нельзя улучшить?» Нужно объяснить, что размер ответа уже $\Theta(n \cdot 4^n)$ в худшем случае. Это главный вопрос, ради которого задачу и дают.
• «Напишите без рекурсии». Это итеративное решение слоями или вариант с очередью.
• «А если нужна только $k$-я комбинация в лексикографическом порядке?» Перебирать не нужно. Каждая позиция — это разряд в смешанной системе счисления с основаниями len(PHONE[d]). Раскладываем $k$ по этим основаниям справа налево и получаем ответ за $O(n)$.
• «Оставьте только слова из словаря». Здесь пригодится префиксное дерево: если текущий префикс не продолжается ни одним словом, ветку можно отсечь сразу. Это уже настоящий бэктрекинг с отсечениями, как в Word Search или N ферзях.
• «Что если цифр 20?» $4^{20} \approx 10^{12}$ строк. Вернуть их списком нельзя, но можно отдавать генератором или по страницам через $k$-ю комбинацию.

Последние два вопроса проверяют, видите ли вы за задачей общий шаблон. Хороший ответ звучит примерно так: «Это декартово произведение. Перебор нельзя сделать быстрее, чем размер выхода, но можно не держать выход в памяти и отсекать ветки, если есть ограничения».

Что запомнить

• Ответ — декартово произведение букв по цифрам, его размер от $3^n$ до $4^n$.
• Бэктрекинг — это «$n$ вложенных циклов», где $n$ становится известно во время выполнения. Состояние: индекс и текущий путь.
• Итеративное решение строит дерево по уровням. itertools.product делает то же самое в одну строку.
• Сложность $O(n \cdot 4^n)$ по времени при любом подходе. Дополнительная память $O(n)$ у рекурсии и генератора.
• Не забывайте if not digits: return [].

Закрепить шаблон удобно на задаче Combination Sum: там то же дерево выбора, но добавляются отсечения по сумме и повторное использование элементов.