Самая длинная общая подстрока в JS

Один из наиболее часто задаваемых вопросов в Frontend Interviews — найти самую длинную общую подстроку. Давайте решим это на простом Javascript.

Теперь обратите внимание, что здесь написано «Подстрока», что означает, что строка должна быть последовательной. Давайте сначала это поймем.

let s1 = "javascript";
let s2 = "java";

Здесь длина LCS равна 4, т.е. «java», общая и непрерывная в обеих строках.

let s1 = "javascript";
let s2 = "scrip";

А здесь LCS — 5, т.е. «сумма».

Это было сделано для того, чтобы вы не перепутали его с Subsequence, что опять-таки является еще одним известным вопросом, который задают интервьюеры. Подпоследовательность означает, что строка НЕ может быть последовательной. Я объясню это подробнее в другом посте.

Подход грубой силы к решению этой проблемы состоял бы в том, чтобы вычислить все возможности s1, затем вычислить все возможности s2, а затем сравнить оба. Оптимизированным подходом было бы использование двумерного массива для решения этой проблемы. Давайте посмотрим, как:

Мы возьмем двумерный массив dp[][] и создадим здесь таблицу, например dp[row][column], и зададим ей значения по мере прохождения обеих строк. Мы взяли s1 и s2 ниже.

s1 = "ABCDGH"
s2 = "ACDGHR"

Здесь мы заполним сетку массива ( dp[][] ) от 0 до длины каждой строки, поэтому строки равны s1, а столбцы - s2.

Мы заполняем первую строку как «0», потому что, если нет символа, LCS будет 0. То же самое с первым столбцом, если в s2 нет символа, тогда LCS будет 0.

Теперь мы должны начать заполнять каждое поле значениями.

Обратите внимание, что мои начальные значения «i» и «j» равны 1.

Начиная с позиции [1][1] логика, которую мы должны использовать для каждого значения, заключается в том, что если i-й элемент s1 равен j-му элементу s2 (символ в строке находит совпадение), то это значение будет «верхнее диагональное значение + 1», иначе мы просто сохраним 0.

По коду условие выглядит так:

if( s1[i - 1] == s2[j - 1] ){
  dp[i][j] = 1 + dp[i-1][j-1];
}
else {
  dp[i][j] = 0;
}

Примечание: dp[i-1][j-1] — диагональное значение

Теперь, следуя этой логике, мы продолжаем заполнять таблицу здесь, и, наконец, мы получим вот такую таблицу,

Мы написали 2 в позиции dp[3][4], потому что символ «D» совпадает в обеих строках, и мы добавляем 1 к его диагональному значению, что делает его 2. Используя ту же логику, мы ввели все значения, и 4 равно наибольшее число в нашей таблице.

Наш ответ — самое большое число в нашей таблице. Это длина самой длинной общей подстроки.

Давайте создадим полное работающее решение на JS ниже. Давайте начнем с создания массива 2d, здесь мы изначально заполняем значения для каждого элемента как 0:

  let n1 = s1.length;
  let n2 = s2.length;
  let dp = Array(n1 + 1)
    .fill(0)
    .map(() => Array(n2 + 1).fill(0));

В сочетании с приведенной выше логикой

let s1 = "abcdgh";
let s2 = "acdghr";

function findLongestCommonSubstring(s1, s2) {
  let n1 = s1.length;
  let n2 = s2.length;
  let dp = Array(n1 + 1)
    .fill(0)
    .map(() => Array(n2 + 1).fill(0));
  let lcs = 0;
  for (let i = 1; i <= n1; i++) {
    for (let j = 1; j <= n2; j++) {
      if (s1[i - 1] === s2[j - 1]) {
        dp[i][j] = 1 + dp[i - 1][j - 1];
        lcs = Math.max(lcs, dp[i][j]);
      }
    }
  }
  return lcs;
}

console.log("Ans: ", findLongestCommonSubstring(s1, s2));

Теперь на выходе будет 4.

Этот подход значительно уменьшил нашу временную сложность до N².

Основная причина, по которой я поместил эту известную проблему в JS, - это для тех, кто ищет работающее решение в JS, поскольку я не мог найти его, когда начал над ним работать.

Не стесняйтесь, дайте мне знать, смог ли я обосновать решение и было ли его легко понять. Мои социальные сети, как показано ниже:

Linkedin — https://www.linkedin.com/in/akshita-tyagi-1a7435b1/

Гитхаб — https://github.com/akshiii

Самая длинная общая подстрока в JS

Большое спасибо за чтение! Не забудьте поставить палец вверх ниже. :)

Вопросы по теме