Solution to LeetCode 718 Maximum Length of Repeated Subarray, LeetCode 1143 Longest Common Subsequence, and LeetCode 1035.
LeetCode 718
Maximum Length of Repeated Subarray (Medium) [link]
Define dp[i][j] as the longest subsequence in both sequences nums1 and nums2 ended at i-1 and j-1. Both i and j start from 1. When nums1[i-1]=nums2[i-1], dp[i][j]=dp[i-1][j-1]+1.
Base cases: dp[0][j]=0 and dp[i][0]=0. dp[0][0]=0.
The dp table is updated along the diagonal lines from the upper left to the down right. dp[i-1][j-1] -> dp[i][j].
class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
dp = [[0] * (len(nums2)+1) for _ in range(len(nums1)+1)]
result = 0
for i in range(1, len(nums1)+1):
for j in range(1, len(nums2)+1):
if nums1[i-1] == nums2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
result = max(result, dp[i][j])
return result
LeetCode 1143
Longest Common Subsequence (Medium) [link]
The subsequence is not necessarily continuous.
Define dp[i][j] as the longest common subsequence of text1 of length [0, i-1] and text1 of length [0, j-1]. If text1[i-1]=text2[j-1], we find a common element, then dp[i][j]=dp[i-1][j-1]+1. If text1[i-1]!=text2[j-1], we find the max of length of longest common subsequence of text1[i-2] and text2[j-1], and longest common subsequence of text1[i-1] and text2[j-2]. Then, dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]).
Base cases: dp[i][0]=dp[0][j]=0. Other values are initialized as zero as well.
Now the updating order is different from LC718. The dp table can be updated along the diagonal lines from the upper left to the down right (dp[i-1][j-1] -> dp[i][j]), and can also be updated from upper cell or left cell (dp[i-1][j]->dp[i][j] and dp[i][j-1]->dp[i][j]).
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
dp = [[0]* (len(text2)+1) for _ in range(len(text1)+1)]
for i in range(1, len(text1)+1):
for j in range(1, len(text2)+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1]+1
else:
dp[i][j] = max(dp[i-1][j],dp[i][j-1])
return dp[-1][-1]
LeetCode 1035
Uncrossed Lines (Medium) [link]
Time complexity O(nm). Space complexity O(nm).
class Solution:
def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
dp = [[0]*(len(nums2)+1) for _ in range(len(nums1)+1)]
for i in range(1, len(nums1) + 1):
for j in range(1, len(nums2) + 1):
if nums1[i-1] == nums2[j-1]:
dp[i][j] = dp[i-1][j-1]+1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[-1][-1]
