Find the length of the longest Common Subsequence

Question

I have a DP based implementation for the Longest Common Subsequence(LCS) problem to find the length of the LCS.

I wanted to know if there is room for improvement in terms of efficiency(space/time).

public int longestCommonSubsequence(char[] firstWord, char[] secondWord) {
        int[][] lcsMatrix = new int[firstWord.length+1][secondWord.length+1];

        for(int i = 0; i < firstWord.length; i++) {
            for(int j = 0; j < secondWord.length ; j++) {

                if (i == 0 || j == 0) {
                    lcsMatrix[i][j] = 0;
                }
                else if(firstWord[i] == secondWord[j]){
                   lcsMatrix[i][j] = lcsMatrix[i-1][j-1]+1;
                }
                else{
                    lcsMatrix[i][j] = Math.max(lcsMatrix[i][j-1],lcsMatrix[i-1][j]);
                }
            }

        }
        return lcsMatrix[firstWord.length-1][secondWord.length-1];
    }

Answer 1

Correctness:

It seems your implementations is incorrect since you are always ignoring the first character.

Here in both loops the range should be closed:

  for(int i = 0; i <= firstWord.length; i++) {
       for(int j = 0; j <= secondWord.length ; j++) { 
           ...
       }
   }

And the second if inside the inner loop should look like this:

else if(firstWord[i - 1] == secondWord[j - 1]) {
    ...
}

finally the function should return this:

 return lcsMatrix[firstWord.length][secondWord.length];

---

DRY your code:

Since in java an array of primitive integers are initialized to zero there is no need for the first if, therefore you can start the loop at i = 1 and j = 1. You could also use a ternary operator after getting rid of the if statement(although some people may prefer the if else).

---

Final code

    public static int longestCommonSubsequence(char[] firstWord, char[] secondWord) {
        int[][] lcsMatrix = new int[firstWord.length + 1][secondWord.length + 1];
        for(int i = 1; i <= firstWord.length; i++) {
            for(int j = 1; j <= secondWord.length ; j++) {
                lcsMatrix[i][j] = (firstWord[i - 1] == secondWord[j - 1]) 
                        ? lcsMatrix[i - 1][j - 1] + 1 
                        : Math.max(lcsMatrix[i][j - 1],lcsMatrix[i - 1][j]);
            }
        }
        return lcsMatrix[firstWord.length][secondWord.length];
    }