Решение проблемы LCS в JavaScript
Задачи JavaScript: от новичка до мастера — Задание №52
Создайте функцию, которая находит самую длинную общую подпоследовательность (LCS) двух строк. Функция должна принимать на вход две строки и возвращать LCS. LCS — это самая длинная последовательность символов, которые появляются в обеих строках в одном и том же порядке.
LCS — самая длинная общая подпоследовательность
Это классическая задача в информатике и динамическом программировании.
Учитывая две последовательности (или строки), цель состоит в том, чтобы найти длину самой длинной подпоследовательности, присутствующей в обеих из них.
Подпоследовательность — это последовательность, которая появляется в одном и том же относительном порядке, но не обязательно последовательно.
Пошаговое решение задачи №52
Шаг 1. Определите функцию LCS
Начнем с определения нашей последней функции под названием longestCommonSubsequence, которая принимает два строковых аргумента: s1 и s2. По завершении он вернет LCS входных строк.
function longestCommonSubsequence(s1, s2) { ... }
Шаг 2. Инициализация переменных длины строки
Добавьте две строки кода, чтобы получить длину строк s1 и s2 и сохранить их в переменных m и n соответственно.
const m = s1.length; const n = s2.length;
Это поможет вам пройтись по каждой строке и настроить таблицу динамического программирования.
Шаг 3. Настройте таблицу динамического программирования
Поскольку вам нужен двумерный массив, инициализируемый переменной dp, где dp[i][j] представляет длину LCS между первыми i символами s1 и первыми j символами s2.
const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
Размер +1 гарантирует, что вы также сможете обрабатывать пустые подстроки.
Каждая ячейка инициализируется нулем в качестве отправной точки.
