tasks for today:
1. 1143.最长公共子序列
2. 1035.不相交的线
3. 53.最大子序和
4. 392.判断子序列 (编辑距离问题)
------------------------------------------------------------------------------
1. 1143.最长公共子序列
300: single, ascending, non-continuity
674: single, ascending, continuity
718: double, continuity
1143: double, non-continuity
in this practice, the key difference from 718 is that, 718 requires contuinuity while this practice does not require contunuity.
The logic "else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])" is added in code snippet.
class Solution:def longestCommonSubsequence(self, text1: str, text2: str) -> int:if (len(text1) == 1 and text1[0] not in text2) or (len(text2) == 1 and text2[0] not in text1): return 0if (len(text1) == 1 and text1[0] in text2) or (len(text2) == 1 and text2[0] in text1): return 1dp = [[0] * (len(text2)+1) for _ in range(len(text1)+1)]result = 0for i in range(1, len(text1)+1):if text1[i-1] == text2[0]:dp[i][1] = 1for j in range(1, len(text2)+1):if text1[0] == text2[j-1]:dp[1][j] = 1for 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] + 1else:dp[i][j] = max(dp[i-1][j], dp[i][j-1])if dp[i][j] > result:result = dp[i][j]return result
2. 1035.不相交的线
This practice is the same with practice 1143, the essence and the code is the same, which both aims to find the sub list having the same sequence and not necesarily continuous.
class Solution:def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:if (len(nums1) == 1 and nums1[0] in nums2) or (len(nums2) == 1 and nums2[0] in nums1): return 1if (len(nums1) == 1 and nums1[0] not in nums2) or (len(nums2) == 1 and nums2[0] not in nums1): return 0dp = [[0] * (len(nums2) + 1) for _ in range(len(nums1) + 1)]result = 0for i in range(1, len(nums1)+1):if nums1[i-1] == nums2[0]:dp[i][1] = 1for j in range(1, len(nums2)+1):if nums1[0] == nums2[j-1]:dp[1][j] = 1for 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] + 1else:dp[i][j] = max(dp[i-1][j], dp[i][j-1])if dp[i][j] > result:result = dp[i][j]return result3. 53.最大子序和
This practice should be compared with practice 674, both of which do not require continuity. The recursive equation aims to compare the bigger one between nums[i] and dp[i-1] + nums[i].
class Solution:def maxSubArray(self, nums: List[int]) -> int:if len(nums) == 1: return nums[0]dp = [0] * len(nums)dp[0] = nums[0]result = nums[0]for i in range(1, len(nums)): dp[i] = max(nums[i], dp[i-1] + nums[i])if dp[i] > result:result = dp[i]return result4. 392.判断子序列
This practice also involve two sequence, so this necessitates a dp table with 2-dim.
This practice is similar to practice 1143, the key difference, the length relationship between s and t. In this practice, the s is no longer than t, so the "dp[i][j] = max(dp[i-1][j], dp[i][j-1])" can be simpified to "dp[i][j] = dp[i][j-1]" when s[i-1] != t[j-1].
class Solution:def isSubsequence(self, s: str, t: str) -> bool:if len(s) == 0: return Trueif len(s) > len(t) or (len(s) == len(t) and s != t): return Falsedp = [[0] * (len(t)+1) for _ in range(len(s)+1)]for i in range(1, len(s)+1):if t[0] in s[:i]:dp[i][1] = 1for j in range(1, len(t)+1):if s[0] in t[:j]:dp[1][j] = 1for i in range(1, len(s)+1):for j in range(1, len(t)+1):if s[i-1] == t[j-1]:dp[i][j] = dp[i-1][j-1] + 1else:# method1: this expression can be same with practice 1143dp[i][j] = max(dp[i-1][j], dp[i][j-1])# method2: while also can be optimized, because in this practice, s should be no longer than the t, so this express can be simplified to following equationdp[i][j] = dp[i][j-1]if dp[-1][-1] == len(s): return Trueelse: return False