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.

base case longest[0][0] = 0

// longest[i][j] indicates the longest common subsequence between s[0- i -1] and t[0-j-1], which might not include i-th character from source and j-th character from t

// longest[i][j] = longest[i - 1][j - 1] + 1 when s[i] == t[j]

// longest[i][j] = max(longest[i-1][j],longest[i][j-1]) when s[i] != t[j]

public class Solution {
  public int longest(String s, String t) {
    // Write your solution here.
    if (s == null || t == null) {
      return 0;
    }

    // longest[i][j] indicates the longest common subsequence between s[0- i -1] and t[0-j-1]
    // longest[i][j] = longest[i - 1][j - 1] + 1 when s[i] == t[j]
    // longest[i][j] = max(longest[i-1][j],longest[i][j-1]) when s[i] != t[j]
    //                 carry on the previous common result
    int[][] longest = new int[s.length() + 1][t.length() + 1];

    for (int i = 1; i <= s.length(); i++) {
      for(int j = 1; j <= t.length(); j++) {
        if (s.charAt(i - 1) == t.charAt(j - 1)) {
          longest[i][j] = longest[i-1][j-1] + 1;

        } else {
          longest[i][j] = Math.max(longest[i-1][j],longest[i][j-1]);
        }
      }
    }
    return longest[s.length()][t.length()];
  }
}