Edit Distance

Средняя№72две строки

Даны два слова. За одну правку можно вставить букву, удалить букву или заменить одну букву другой. Нужно найти наименьшее число правок, чтобы превратить первое слово во второе. Наш пример: «pans» → «span» — 2 правки: вставить s в начало и удалить s в конце.

72 Edit DistanceРазбор · 1×

Пример: a = «pans», b = «span»: те же буквы, сдвинутые на одно место. Смотрите, как последняя клетка выбирает удаление, а не замену.

spanpans
заполненоэтот шаг, сравниваемые буквыберём отсюдаответ и его путь

dp[i][j]: наименьшее число правок, чтобы первые i букв pans превратить в первые j букв span

01/40
сначала · назад · пуск · шаг
Скорость
1function minEdits(a, b):
2 dp = table of len(a) + 1 by len(b) + 1
3 for i from 0 to len(a): dp[i][0] = i // delete all
4 for j from 0 to len(b): dp[0][j] = j // insert all
5 for i from 1 to len(a):
6 for j from 1 to len(b):
7 if a[i - 1] == b[j - 1]:
8 dp[i][j] = dp[i - 1][j - 1]
9 else:
10 dp[i][j] = 1 + min(dp[i - 1][j - 1],
11 dp[i - 1][j],
12 dp[i][j - 1])
13 return dp[len(a)][len(b)]
состояние
dp
[[–, –, –, –, –], [–, –, –, –, –], [–, –, –, –, –], [–, –, –, –, –], [–, –, –, –, –]]
i
–
j
–
историянажмите шаг, чтобы вернуться

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

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

  1. Смотрим на последние буквы двух префиксов. Если они равны, оставить их ничего не стоит, и клетка копирует диагональ.
  2. Если разные, последняя правка — одна из трёх: заменить букву a на букву b (диагональ), удалить букву a (сверху) или вставить букву b (слева). Клетка на один больше самого дешёвого из них.
  3. Края точные: пустому префиксу нужно столько правок, сколько букв в другом префиксе. Остальные клетки строятся из уже заполненных, поэтому правая нижняя клетка — настоящий минимум.

Сложность

Время O(n × m) для слов длины n и m: по клетке на каждую пару префиксов, каждая по трём соседям. Память O(n × m) на таблицу; хватит строки сверху и текущей, O(m).

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

Решить на LeetCode ↗

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