Где применяется
1. Задача
Прошлый шаг искал самую длинную возрастающую цепочку внутри одного списка. Теперь списков два. Нужна самая длинная цепочка элементов, которая встречается в обоих списках в одном и том же порядке.
Элементы не обязаны стоять рядом, пропускать можно. Ты оставляешь только те элементы, которые есть в обеих последовательностях, и сохраняешь их порядок.
Возьми слова "ABCBDAB" и "BDCAB". Самое длинное, что есть в обоих по порядку, это "BCAB", длина 4. Пропуски разрешены, поэтому B, C, A и B можно брать из далёких друг от друга мест, лишь бы порядок сохранялся.
Именно это git diff делает внутри. Он берёт две версии файла и находит самый длинный набор строк, которые остались прежними и идут в том же порядке. Всё остальное он показывает как изменения.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 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 получается из трёх соседей, а при совпадении берётся диагональ.
Задача урока слово в слово.
Непересекающиеся линии соединяют равные числа в одном порядке, так что ответ это длина самой длинной общей подпоследовательности двух массивов.
Всё, что вне общей части, удаляется, так что ответ это сумма длин минус удвоенная длина общей подпоследовательности.
Заполни таблицу, потом пройди назад от угла и пиши каждую общую букву один раз, а каждую другую по мере прохода.