Problem

  • Given two strings, S of length m and T of length n
  • Write an algorithm to find the length of the longest common subsequence (LCS) of both S and T

Example

  • Input: given two strings "XMJYAUZ" and "MZJAWXU". Expected output: 4 (the LCS is "MJAU")

Approach: Bottom Up Dynamic Programming

  • Optimal substructure: L(i, j) = L(i-1, j-1) + 1 if S(i-1) == T(j-1) with L(i, j) is the length of the common subsequence at character S(i) and T(j)

    For the above example, the LCS "MJAU" has the length at the last common character U of both S and T, L(6, 7), equals to the length at the immediate preceding common character A, L(5, 4), plus 1

  • Bottom up filling the 2D array L[m+1][n+1]. The length of the LCS is at L[m][n]

Implementation


Complexity

  • Time complexity: O(mn)
  • Space complexity: O(mn)