# Find the length of the longest Common Subsequence

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


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


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