2
\$\begingroup\$

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];
    }
\$\endgroup\$
2
\$\begingroup\$

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];
    }
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.