JavaScript最长公共子序列

Question

我有一个算法，必须按以下方式返回结果：

/*
"ABAZDC", "BACBAD" => ABAD
"AGGTAB", "GXTXAYB" => GTAB
"aaaa", "aa" => "aa"
"", "..." => ""
"ABBA", "ABCABA" => "ABBA"
*/

我开发的代码没有返回这些结果。我该怎么解决呢？

console.log(solution('ABAZDC', 'BACBAD')) 

function solution(str1, str2) {
  str1 = str1.split('')
  str2 = str2.split('')  
  
  const output = []
 
  for(let i = str1.length -1; i >= 0; i--) {   
    for(let j = str2.length -1; j >= 0; j--) {
      if( str2[j] === str1[i] ) {
        output.push(str2[j]) 
        break
      }      
    } 
    
  }
  
  return output.reverse().join('')
 
}

注：

这是youtube上的一个解决方案。但对我来说，对于那些不熟悉这个问题的人来说，这个解决方案是复杂的。我现在想找个更简单的解决办法。这将是一个不包含递归函数或回忆录的解决方案。

https://www.youtube.com/watch?v=10WnvBk9sZc&feature=youtu.be

Answer 1

给您!您需要创建带有"A.length + 1“行和"B.length + 1”列的矩阵(第0索引中的元素都是0)，而矩阵中最右边的最低数将是您的答案。在这个例子中-

0, 0, 0, 0, 0, 0
0, 1, 1, 1, 1, 1
0, 1, 2, 2, 2, 2
0, 1, 2, 2, 2, 3

function longestCommonSubsequence(a, b) {
    const matrix = Array(a.length + 1).fill().map(() => Array(b.length + 1).fill(0));
    for(let i = 1; i < a.length + 1; i++) {
        for(let j = 1; j < b.length + 1; j++) {
            if(a[i-1] === b[j-1]) {
                matrix[i][j] = 1 + matrix[i-1][j-1];
            } else {
                matrix[i][j] = Math.max(matrix[i-1][j], matrix[i][j-1]);
            }
        }
    }
    return matrix[a.length][b.length];
}

let a = [2,3,4];
let b = [2,3,7,8,4];

console.log(longestCommonSubsequence(a,b));

Answer 2

我建议你先看这个视频，解决方案在里面解释得很好。https://www.youtube.com/watch?v=ASoaQq66foQ

代码正在返回字符串的最大长度，您可以修改它以满足您的目的。

function longestCommonSubsequence(s1, s2) {
  // string to array
  const arr1 = [...s1]
  const arr2 = [...s2]

  // define n x m sized array filled with 0's
  let matrix = [...Array(arr1.length+1)].map(e => Array(arr2.length+1).fill(0))

  // fill the matrix
  for(let i = 1; i <= arr1.length; i++) {
      for(let j = 1; j <= arr2.length; j++) {
          if(arr1[i-1] == arr2[j-1]) { matrix[i][j] = matrix[i-1][j] + 1}
          else matrix[i][j] = Math.max(matrix[i-1][j], matrix[i][j-1])
      }
  }

  // return the max which is at the right bottom corner of the matrix
  return matrix[matrix.length-1][matrix[0].length-1]
}

Answer 3

函数将为给定的两个字符串返回最长的子字符串。

function longestCommonSubstring(str1, str2) {

    if (str1 === str2) return str2;
    if (!str2.split('').some(ele => str1.includes(ele))) return '';
    let commonSubStr = '';
    let storage = [];
    const strLength = str2.length;

    for (let i = 0; i < strLength; i++) {

        let ind = str1.indexOf(str2[i]);
        if (ind === -1) continue;

        for (let j = i, k = ind; j < strLength; j++, k++) {
            if (str2[j] === str1[k])
                commonSubStr += str2[j];
            else {
                storage.push(commonSubStr);
                commonSubStr = '';
            }
        }
        storage.push(commonSubStr);
        commonSubStr = '';
    }

    return storage.sort((a, b) => b.length - a.length)[0].length;
}