Где применяется
1. Задача
У тебя два слова. Первое нужно превратить во второе за наименьшее число правок по одному символу. Правки бывают трёх видов: вставить символ, удалить символ или заменить один символ другим. Каждая правка стоит 1.
Преврати "horse" в "ros". Один дешёвый способ: заменить h на r, удалить o, удалить e. Это 3 правки, и меньше не получится. Значит, ответ 3.
Это число называют редакционным расстоянием, или расстоянием Левенштейна. Оно показывает, насколько две строки далеки друг от друга. На нём построена проверка орфографии. Если ты напечатал "recive", исправление "receive" отстоит на 1 правку (вставить одну e). Поэтому оно выигрывает у слов вроде "believe", до которого 3 правки.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитКак узнать
Эти слова в условии значат этот паттерн
- самая длинная возрастающая подпоследовательность
- самая длинная общая подпоследовательность двух строк
- минимум правок, чтобы превратить одну строку в другую
- сохранить относительный порядок, можно пропускать элементы
- diff или выравнивание двух последовательностей
Похоже, но не то
- Динамическое программирование (1-D) (Dynamic programming (1-D))
Там хватает одного индекса. Сравнению двух последовательностей нужны два.
- DP на строках (word break) (DP on strings (word break))
Та страница режет одну строку на куски. Эта выравнивает две последовательности.
- Бинарный поиск (массив) (Binary search (array))
Версия возрастающей подпоследовательности за n log n использует бинарный поиск. Табличная версия медленнее.
- Два указателя (в одну сторону) (Two pointers (same direction))
Проверке, является ли строка подпоследовательностью, таблица не нужна. Поиску наибольшей общей нужна.
Одна последовательность из n элементов стоит O(n²) времени. Две длины n и m стоят O(nm), и хватает одной строки памяти.
На LeetCode
Задачи, где две строки сравнивают клетка за клеткой со стоимостью или счётом на каждом шаге, например правки, сопоставление со звёздочкой или число способов собрать одну строку из другой. Таблица хранит ответ для каждой пары префиксов, а пустые префиксы заполняют первую строку и первый столбец.
Задача урока. Вставка, удаление и замена это левая, верхняя и диагональная клетки плюс один.
Клетка i, j отвечает, собирают ли первые i букв s1 и первые j букв s2 первые i + j букв s3, и берётся из верхней или левой клетки.
В клетках хранятся счётчики. При совпадении букв сложи диагональ и верхнюю клетку, а пустая цель даёт 1 во всём первом столбце.
Если текст идёт по строкам, а шаблон по столбцам, клетка со звёздочкой берётся из верхней (звёздочка съедает ещё одну букву) или из левой (она пустая). Базовая строка остаётся true, только пока в шаблоне одни звёздочки.