Почему это работает
- BFS идёт по уровням, а steps считает слова до текущего уровня, поэтому первый раз, когда появилось конечное слово, steps + 1 — самая короткая лестница.
- Слово убираем из множества в момент, когда кладём в очередь: второе слово того же уровня, которое ведёт к нему, его уже не находит, поэтому дважды ничего не попадает в очередь и отдельный visited не нужен.
- Если конечного слова нет в списке, лестница не может на нём закончиться, и ответ 0 ещё до поиска.
Сложность
Время O(n · 26 · L²) для n слов длины L: каждое слово попадает в очередь один раз и пробует 26 букв на каждом из L мест, а собрать и найти каждое новое слово — O(L). Память O(n) на множество и очередь.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗