javascript least common subsequence, implementing the cache

I am trying to implement the javascript version of the 'Longest Common Subsequence' problem. I am following the java implementation here:

// working solution
class BottomUp {
  public int longestCommonsubsequenceLength(String s1, String s2) {
    int cache[][] = new int[s2.length() + 1][s1.length() + 1];

    for (int s2Row = 0; s2Row <= s2.length(); s2Row++) {
      for (int s1Col = 0; s1Col <= s1.length(); s1Col++) {
        if (s2Row == 0 || s1Col == 0) {
          cache[s2Row][s1Col] = 0;
        } else if (s2.charAt(s2Row - 1) == s1.charAt(s1Col - 1)) {
          cache[s2Row][s1Col] = cache[s2Row - 1][s1Col - 1] + 1;
        }
        else {
          cache[s2Row][s1Col] = Math.max(cache[s2Row - 1][s1Col], cache[s2Row][s1Col - 1]);
        }
      }
    }
    return cache[s2.length()][s1.length()];
  }
}

However, when I try to initialize the and access the multi-dimensional array:

int cache[][] = new int[s2.length() + 1][s1.length() + 1]; and access it, it tells me that is undefined.

Here is my attempt:

var longestCommonSubsequence = function(s1, s2) {
    let cache = [];
    let max = 0;

    // ***initialize cache***
    for(let i = 0; i <= s1.length; i++) {
        cache.push(new Array(s2.length + 1).fill(0));
    }

    for (let s2Row = 0; s2Row <= s2.length; s2Row++) {
      for (let s1Col = 0; s1Col <= s1.length; s1Col++) {
        if (s2Row == 0 || s1Col == 0) {
          cache[s2Row][s1Col] = 0; // crashes here. 'Cannot set property '0' of undefined

        } else if (s2.charAt(s2Row - 1) == s1.charAt(s1Col - 1)) {
          cache[s2Row][s1Col] = cache[s2Row - 1][s1Col - 1] + 1;
        }
        else {
          cache[s2Row][s1Col] = Math.max(cache[s2Row - 1][s1Col], cache[s2Row][s1Col - 1]);
        }
      }
    }

    return cache[s2.length][s1.length];
};

How can I implement the array in the way that is done in the Java solution?

edit:

It seems to work with some inputs, e.g. String 1: "abcde" String 2: "ace"

But fails with others, e.g.String 1: "pmjghexybyrgzczy" String 2: "hafcdqbgncrcbihkd"

Thanks for any help.

1 answer

  • answered 2019-09-10 02:35 Mordred

    The issue is that the sizes used for your array initialization are reversed. I don't know if the Java version actually works correctly, but your Javascript works correctly if s1 and s2 are the same length, or if s2 is longer. If s1 is longer than s2 it crashes because it's trying to index outside the bounds you created.

    The solution was to change your initialization so that the row array is based off the length of s2 and the columns are off the length of s1. Yours was going out of bounds and referencing cache[5][0] when your cache was of size [4][5] (for example).

    Working code:

    var longestCommonSubsequence = function(s1, s2) {
        let cache = [];
        let max = 0;
    
        // ***initialize cache***
        for(let i = 0; i <= s2.length; i++) {
            cache.push(new Array(s1.length + 1).fill(0));
        }
    
        for (let s2Row = 0; s2Row <= s2.length; s2Row++) {
          for (let s1Col = 0; s1Col <= s1.length; s1Col++) {
            if (s2Row == 0 || s1Col == 0) {
              cache[s2Row][s1Col] = 0; 
    
            } else if (s2.charAt(s2Row - 1) == s1.charAt(s1Col - 1)) {
              cache[s2Row][s1Col] = cache[s2Row - 1][s1Col - 1] + 1;
            }
            else {
              cache[s2Row][s1Col] = Math.max(cache[s2Row - 1][s1Col], cache[s2Row][s1Col - 1]);
            }
          }
        }
    
        return cache[s2.length][s1.length];
    };
    
    console.log(longestCommonSubsequence('abc', 'bcasdf'));
    console.log(longestCommonSubsequence('adcfghj', 'abcd'));
    console.log(longestCommonSubsequence('abcd', 'bced'));
    console.log(longestCommonSubsequence('pmjghexybyrgzczy', 'hafcdqbgncrcbihkd'));