JavaScript Longest common subsequence

Question

I have an algorithm that must return the result as follow:

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

The code that I developed didn't return these results. How can I solve it?

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('')
 
}

NOTE:

Here's a solution on youtube. But for me, this solution is complicated for those who are not familiar with this problem. I'd like to see a simpler solution for now. It would be a solution that does NOT contain recursive functions or memoization.

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

Answer 1

Here you go ! You need to create matrix with "A.length + 1" rows and "B.length + 1" columns (elements in 0th index are all 0s) and the rightest lowest number in your matrix will be your answer. In this example -

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

I recommend you to watch this video first, the solution is very well explained in it. https://www.youtube.com/watch?v=ASoaQq66foQ

The code is returning the max length of the string, you can modify it in order to serve your purpose.

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]
}