Longest Common Sequence between two strings

Find the length of longest common subsequence of two given strings.

Assumptions

• The two given strings are not null

Examples

• S = “abcde”, T = “cbabdfe”, the longest common subsequence of s and t is {‘a’, ‘b’, ‘d’, ‘e’}, the length is 4.

High Level:

What to memo:

M[i][j] = longest length of subsequence from first i chars of s1, first j chars of s2

Base case:

M[0][j] = 0 and M[i][0] = 0

Induction rule:

if s1[i] == s2[j], M[i][j] = M[i-1][j-1] + 1

else M[i][j] = max(M[i-1][j], M[i][j-1])

public class Solution {
  public int longest(String source, String target) {
    //edge case
    if(source.length() == 0 || target.length() == 0) return 0;

    int[][] M = new int[source.length()][target.length()];

    // base case
    M[0][0] = source.charAt(0) == target.charAt(0) ? 1 : 0;

    for (int i = 1 ; i < source.length(); i++) {
      M[i][0] = source.charAt(i) == target.charAt(0) ? 1 : M[i-1][0];
    }

    for (int j = 1 ; j < target.length(); j++) {
      M[0][j] = source.charAt(0) == target.charAt(j) ? 1 : M[0][j-1];
    }
    
    //iterate row by row
    for(int i = 1; i < source.length();i++){ //rows
      for(int j = 1; j < target.length(); j++){ //columns
        if(source.charAt(i) == target.charAt(j)){
          M[i][j] = M[i-1][j-1] + 1;
        } else {
          M[i][j] = Math.max(M[i-1][j], M[i][j-1]);
        }
      }
    }

    return M[source.length() - 1][target.length() - 1];
  }
}

TC: O(N^2) 2D memo

SC: O(N^2) 2D memo

Mistakes made:

top row and left most column do not all equal 0. It can inherit from neighbor if matched.