Longest Common Subsequence
This problem is very practical. In Unix utility
diff, a line of one file is compared w/ that of another. In
git diff, a line of newer version is compared w/ that of older version. In this problem, we simply compute the common chars of 2 strings.
Let and be lengths of
Initial Wrong Solution
Following is a wrong solution because I didn't consider the case that a subsequence later seen can be longer than a subsequence earlier seen.
This test case failed b/c
p is before
qr in shorter
text1 while after
text1 = "oxcpqrsvwf" text2 = "shmtulqrypy"
def longestCommonSubsequence(self, text1: str, text2: str) -> int: lcs = 0 l = 0 shorter = text1 if len(text1) <= len(text2) else text2 longer = text1 if len(text1) > len(text2) else text2 for i in range(0, len(shorter)): # find the shorter ith elt in longer[l:] j = longer[l:].find(shorter[i]) if j!=-1: l=j+1 lcs+=1 return lcs
Thus, this problem should be solved by DP (iterative/recursive w/ memoization).
# Iterative DP (squared space)
As explained in this video, I construct a matrix to store the length of longest common subsequence seen so far. If the two chars match,
M[i-1][j-1]+1 ; o.w., it's the max of
M[i][j-1]. At the end of for loop, return
def longestCommonSubsequence(self, text1: str, text2: str) -> int: n,m = len(text1),len(text2) M = [ * (m + 1) for _ in range(n + 1)] for i in range(1, n+1): for j in range(1, m+1): if text1[i-1]==text2[j-1]: M[i][j] = M[i-1][j-1]+1 else: M[i][j] = max(M[i-1][j], M[i][j-1]) return M[-1][-1]
# Iterative DP (linear space)
This is similar to iterative DP, but has less space complexity: smaller matrix only needs previous row to calculate current row, so only 2 rows are needed.
Please note that the commented line
M,M = M,M doesn't work because Python list is copy by reference, not by value.
def longestCommonSubsequence(self, text1: str, text2: str) -> int: n,m = len(text1),len(text2) # find the shorter string s = text1 if n<=m else text2 l = text1 if n>m else text2 M = [*(len(s)+1) for i in range(2)] for i in range(1,len(l)+1): for j in range(1,len(s)+1): if s[j-1]==l[i-1]: M[i%2][j] = M[1-i%2][j-1] + 1 else: M[i%2][j] = max(M[1-i%2][j],M[i%2][j-1]) # M,M = M,M return M[-1][-1]
# Recursive DP (REDO)