Почему это работает
- Ген — состояние, мутация — ребро между генами банка, которые отличаются одной буквой, поэтому BFS доходит до каждого гена впервые за наименьшее число мутаций.
- Того, что конечный ген есть в банке, мало: две разные буквы — это две мутации, и промежуточный ген тоже должен быть в банке.
- Гены выходят из очереди по возрастанию мутаций, поэтому, когда выходит конечный, его расстояние — ответ; если очередь кончилась раньше, пути нет и ответ -1.
Сложность
Время O(b² · L) для банка из b генов длины L: каждый ген берём из очереди один раз и сравниваем по буквам со всем банком. Память O(b) на dist и очередь.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗