LeetCode 718. Maximum Length of Repeated Subarray
问题描述
1 | Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays. |
思路
这道题给了我们两个数组A和B,让返回连个数组的最长重复子数组。那么如果将数组换成字符串,实际这道题就是求 Longest Common Substring 的问题了。注意需要跟最长子序列 Longest Common Subsequence 区分开。 既然是子数组,那么重复的地方一定是连续的。对于这种求极值的问题,动态规划 Dynamic Programming 一直都是一个很好的选择,这里使用一个二维的 DP 数组,其中 dp[i][j] 表示数组A的前i个数字和数组B的前j个数字的最长子数组的长度,如果 dp[i][j] 不为0,则A中第i个数组和B中第j个数字必须相等,比对于这两个数组 [1,2,2] 和 [3,1,2],dp 数组为:
1 | 3 1 2 |
- 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)
code
1 | class Solution: |
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.
问题描述
1 | Given two strings text1 and text2, return the length of their longest common subsequence. |
思路
- 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])
code
1 | class Solution: |
Leetoce 583. Delete Operation for Two Strings
问题描述
1 | Given two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same, where in each step you can delete one character in either string. |
思路
这题实际上是求两个字符串的 Longest Common Subsequence. 然后用两个字符串的长度和减去 2*LCS. DP的思路与上题一样。
code
1 | class Solution: |
Leetcode 1092. Shortest Common Supersequence
问题描述
1 | Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If multiple answers exist, you may return any of them. |
思路
code
class Solution:
def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
if not str1 or not str2:
return ""
dp = [[0] * (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])
reference from https://zxi.mytechroad.com/blog/dynamic-programming/leetcode-1092-shortest-common-supersequence/