Letter Combinations of a Phone Number

Средняя№17буква за буквой

На старой кнопочной клавиатуре каждая цифра от 2 до 9 обозначает три или четыре буквы. Дана строка таких цифр; нужно вернуть все слова, которые ей можно набрать, по одной букве на цифру, в любом порядке, а для пустой строки — ничего. Наш пример: "38", где 3 — это d, e, f, а 8 — t, u, v, даёт 9 слов: dt, du, dv, et, eu, ev, ft, fu, fv.

17 Letter Combinations of a Phone NumberРазбор · 1×

Пример: все слова, набранные "38". Смотрите на шаг после того, как сохранено dv: d убирается, и на первое место встаёт e — для следующих трёх слов.

[ ]ddtdudveeteuevfftfufv3→def8→tuvпуть—результаты—
ещё не былипо пути сюда; буква в путиэтот шагсохранённое словозавершено или только что убрано

Составляем все слова, которые набирают клавиши 38

01/57
сначала · назад · пуск · шаг
Скорость
1function letterCombinations(digits):
2 if digits is empty: return []
3 path = []
4 results = []
5 spell(0)
6 return results
7
8function spell(i):
9 if i == len(digits):
10 add path joined to results
11 return
12 for letter in letters of digits[i]:
13 path.add(letter)
14 spell(i + 1)
15 path.removeLast()
состояние
i
–
letter
–
path
–
results
–
нажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Вызов i выбирает букву для цифры i и передаёт остальное вызову i + 1, поэтому в дереве по уровню на цифру и по ветке на букву: каждое слово — один путь от корня до листа.
  2. Буква убирается, когда вызов вернулся, и освобождает место, поэтому следующая буква той же цифры пробуется с теми же буквами перед ней.
  3. Слово сохраняется, только когда i дошёл до конца, поэтому в нём всегда ровно по одной букве на цифру.

Сложность

Время O(n × 4ⁿ) для n цифр: до 4ⁿ слов, каждое склеивается за n шагов. Память O(n) помимо ответа: путь и стек вызовов глубиной n.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.