Цепочка правок гена

Средняя

Ген записан строкой ровно из 8 символов, каждый из которых — A, C, G или T. Одна правка — замена одного символа строки на другой. Лаборатория хочет превратить ген start в ген goal последовательностью правок. После каждой правки должен получаться жизнеспособный ген, то есть строка из списка allowed. Сам start считается жизнеспособным, даже если его нет в списке. Верните наименьшее число правок, за которое это можно сделать, или -1, если это невозможно.

Пример 1

start="GATTACAA", goal="GATTACCC", allowed=["GATTACCA", "GATTACCC"] → 2

GATTACAA → GATTACCA → GATTACCC: две правки, и обе промежуточные строки есть в allowed.

Пример 2

start="GATTACAA", goal="GATTACCC", allowed=["GATTACCC"] → -1

До цели две буквы разницы, а промежуточного разрешённого гена нет — ответ -1.

Пример 3

start="CCCCCCCC", goal="CCCCCCCC", allowed=[] → 0

Ограничения

len(start) == len(goal) == len(allowed[i]) == 8
0 ≤ len(allowed) ≤ 10
Строки состоят только из символов A, C, G, T

Встречал эту задачу на настоящем собесе?

Решили0

Пробовали0

Отправок0

Принято—

Темы

Breadth-First Search Hash Table String

Вход

start="GATTACAA", goal="GATTACCC", allowed=["GATTACCA", "GATTACCC"]

Ожидается

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 61 тест на сервере, включая скрытые.