Word Ladder

Сложная№127состояния

Даны начальное слово, конечное слово и список слов той же длины. Лестница идёт от начального слова к конечному, меняя по одной букве, и каждое слово после первого должно быть в списке. Вернуть, сколько слов в самой короткой лестнице, считая оба конца, или 0, если её нет. Наш пример: sit → pan со списком [pit, sat, pat, pan] — ответ 4.

127 Word LadderРазбор · 1×

Пример: самая короткая лестница от sit до pan через список [pit, sat, pat, pan], в словах.

1 слово2 слова3 слова4 словаsitwordSetpitsatpatpanочередьначало слева—
в множестве, не достигнутождёт в очередитекущее словона одну букву дальшеготовоубрано из множества

Кладём список в множество: {pit, sat, pat, pan}

01/37
сначала · назад · пуск · шаг
Скорость
1function ladderLength(begin, end, words):
2 wordSet = set(words)
3 if end not in wordSet:
4 return 0
5 queue = [begin]
6 steps = 1
7 while queue is not empty:
8 repeat queue.size times:
9 word = queue.popFront()
10 for next in oneLetterAway(word):
11 if next == end:
12 return steps + 1
13 if next in wordSet:
14 wordSet.remove(next)
15 queue.pushBack(next)
16 steps = steps + 1
17 return 0
состояние
wordSet
{pit, sat, pat, pan}
queue
–
steps
–
word
–
next
–
историянажмите шаг, чтобы вернуться

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

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

  1. BFS идёт по уровням, а steps считает слова до текущего уровня, поэтому первый раз, когда появилось конечное слово, steps + 1 — самая короткая лестница.
  2. Слово убираем из множества в момент, когда кладём в очередь: второе слово того же уровня, которое ведёт к нему, его уже не находит, поэтому дважды ничего не попадает в очередь и отдельный visited не нужен.
  3. Если конечного слова нет в списке, лестница не может на нём закончиться, и ответ 0 ещё до поиска.

Сложность

Время O(n · 26 · L²) для n слов длины L: каждое слово попадает в очередь один раз и пробует 26 букв на каждом из L мест, а собрать и найти каждое новое слово — O(L). Память O(n) на множество и очередь.

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

Решить на LeetCode ↗

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