Почему это работает
- Смотрим на последние буквы двух префиксов. Если они равны, оставить их ничего не стоит, и клетка копирует диагональ.
- Если разные, последняя правка — одна из трёх: заменить букву a на букву b (диагональ), удалить букву a (сверху) или вставить букву b (слева). Клетка на один больше самого дешёвого из них.
- Края точные: пустому префиксу нужно столько правок, сколько букв в другом префиксе. Остальные клетки строятся из уже заполненных, поэтому правая нижняя клетка — настоящий минимум.
Сложность
Время O(n × m) для слов длины n и m: по клетке на каждую пару префиксов, каждая по трём соседям. Память O(n × m) на таблицу; хватит строки сверху и текущей, O(m).
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗