educative.io

O(min(M, N)) space complexity

Courses
,
#1

I hate when the solution does not cover it. Here is my solution:

class LCS {
  static int findLCSLength(String s1, String s2) {
    if (s1 == null || s2 == null) {
      return 0;
    } else if (s1.length() < s2.length()) {
      return findLCSLength(s2, s1);
    }
    int[] dpLast = new int[s2.length() + 1];
    for (int i = 1; i <= s1.length(); i++) {
      int[] dp = new int[s2.length() + 1];
      for (int j = 1; j <= s2.length(); j++) {
        dp[j] = s1.charAt(i - 1) == s2.charAt(j - 1)
            ? dpLast[j - 1] + 1
            : Math.max(dp[j - 1], dpLast[j]);
      }
      dpLast = dp;
    }
    return dpLast[s2.length()];
  }
}