Minimum Genetic Mutation

Средняя№433состояния

Ген — строка из 8 букв, каждая A, C, G или T. Одна мутация меняет одну букву, и по пути разрешены только гены из данного банка; стартовый ген в банке быть не обязан. Найти наименьшее число мутаций от стартового гена до конечного или -1, если так нельзя. Наш пример: старт AAGGTTCC, конец AAGCTTCA, банк [AAGCTTCA, TAGGTTCC, AAGGTTCA] — ответ 2.

433 Minimum Genetic MutationРазбор · 1×

Пример: наименьшее число мутаций по одной букве от AAGGTTCC до AAGCTTCA через банк [AAGCTTCA, TAGGTTCC, AAGGTTCA].

0 мутаций1 мутация2 мутацииAAGGTTCCбанкAAGCTTCATAGGTTCCAAGGTTCAочередьначало слева—
не достигнутждёт в очередитекущий генпроверяемый ген банкаготов

До старта AAGGTTCC — 0 мутаций

01/33
сначала · назад · пуск · шаг
Скорость
1function minMutation(start, end, bank):
2 dist = {start: 0}
3 queue = [start]
4 while queue is not empty:
5 cur = queue.popFront()
6 if cur == end:
7 return dist[cur]
8 for gene in bank:
9 if gene not in dist and oneApart(cur, gene):
10 dist[gene] = dist[cur] + 1
11 queue.pushBack(gene)
12 return -1
состояние
dist
{AAGGTTCC: 0}
queue
–
cur
–
gene
–
историянажмите шаг, чтобы вернуться

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

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

  1. Ген — состояние, мутация — ребро между генами банка, которые отличаются одной буквой, поэтому BFS доходит до каждого гена впервые за наименьшее число мутаций.
  2. Того, что конечный ген есть в банке, мало: две разные буквы — это две мутации, и промежуточный ген тоже должен быть в банке.
  3. Гены выходят из очереди по возрастанию мутаций, поэтому, когда выходит конечный, его расстояние — ответ; если очередь кончилась раньше, пути нет и ответ -1.

Сложность

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

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

Решить на LeetCode ↗

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