## LeetCode 718. Maximum Length of Repeated Subarray

### 思路

• dp[i][j] := max length of (A[0:i], B[0:j])
• dp[i][j] = dp[i – 1][j – 1] + 1 if A[i-1] == B[j-1] else 0
• Time complexity: O(m*n)
• Space complexity: O(m*n) -> O(n)

## Leetoce 1143. Longest Common Subsequence

A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, “ace” is a subsequence of “abcde” while “aec” is not). A common subsequence of two strings is a subsequence that is common to both strings.

### 思路

• dp[i][j] stands for length of LCS between text1 up to i and text2 up to j.
• dp[i][j] = dp[i-1][j-1] + 1 if text1[i] == text2[j]
• Otherwise, dp[i][j] = max(dp[i][j-1], dp[i-1][j])

## Leetcode 1092. Shortest Common Supersequence

### 思路 ### code

class Solution:
def shortestCommonSupersequence(self, str1: str, str2: str) -> str:

if not str1 or not str2:
return ""

dp = [ * (len(str2)+1) for i in range(len(str1)+1)]

# dp[i][j] -->  i: str1, j: str2

for i in range(1,len(str1)+1):
for j in range(1,len(str2)+1):
if str1[i-1] == str2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j],dp[i][j-1])

l1 = len(str1); l2 = len(str2)

res = []

while l1 or l2:
if not l1:
char = str2[l2-1]
l2 -= 1
elif not l2:
char = str1[l1-1]
l1 -= 1
elif str1[l1-1] == str2[l2-1]:
char = str1[l1-1]
l1 -= 1
l2 -= 1
elif dp[l1-1][l2] == dp[l1][l2]:
char = str1[l1-1]
l1 -= 1
elif dp[l1][l2-1] == dp[l1][l2]:
char = str2[l2-1]
l2 -= 1

res.append(char)

return "".join(res[::-1])

Donate article here