JavaScript 最长公共(public)子序列

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));