Код Senior Динамическое программирование обновлено
Расстояние редактирования
Условие
Минимальное число вставок, удалений и замен, чтобы превратить одну строку в другую.
Примеры
editDistance("horse", "ros") // 3
editDistance("intention", "execution") // 5
editDistance("", "") // 0
Как подойти
Эталонная двумерная динамика. Каждый сосед отвечает за свою операцию: диагональ - замена, верх - удаление, левый - вставка. База заполняется длинами префиксов. Свёртка до двух строк даёт O(min(n,m)) памяти. На этом же принципе работают подсветка различий и нечёткий поиск.
Подсказки: 2
- Три операции - три соседа в таблице: диагональ, верх, левый.
- Нулевая строка и столбец - превращение в пустую строку.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.