Leetcode 718 longest common substring

Give two arrays of integers nums1 and nums2 , return In two arrays Public 、 The length of the longest subarray .

Example 1：

Input ：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output ：3
explain ： The longest common subarray is [3,2,1] .
Example 2：

Input ：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
Output ：5

Consider the violence act first , The idea of using prefixes or suffixes , enumeration nums1[i] and nums2[j], Find the string that ends with them nums1[:i+1] and nums2[:j+1] The longest common suffix of , Take the maximum value among all enumeration results . Time complexity O(n3)

# class Solution(object):
# def findLength(self, nums1, nums2):
# """
# :type nums1: List[int]
# :type nums2: List[int]
# :rtype: int
# """
# tot = 0
# for i in range(len(nums1)):
# for j in range(len(nums2)):
# k = 0
# while (i + k < len(nums1)) and (j + k < len(nums2)) and (nums1[i+k] == nums2[j+k]):
# k += 1
# tot = max(tot, k)
# return tot 
class Solution(object):
    def findLength(self, nums1, nums2):
        """ :type nums1: List[int] :type nums2: List[int] :rtype: int """
        tot = 0
        for i in range(len(nums1)):
            for j in range(len(nums2)):
                k = 0
                while (i - k >= 0) and (j - k >= 0) and (nums1[i-k] == nums2[j-k]):
                    k += 1
                tot = max(tot, k)
        return tot 

It can be seen that the reason for the high complexity is ,nums1[i] and nums2[j] Repeatedly compared , If you want to compare , In the future, there is no need to compare directly , Then consider dynamic programming . Unlike subsequences ’abc’ And ’abd’ The longest common substring is ’ab’, The length is 2, But after adding a bit ,‘abcd’ And ’abdd’ Even if the last one is the same , The length of the longest substring is still 2. So our dp[i][j] I want to change the meaning of , Is to separate with nums1[i-1] and nums2[j-1] The longest common suffix of the ending string , The end result is all dp[i][j] The maximum of the values .

State transition equation , Two considerations ：
When text1[i - 1] == text2[j - 1] when , It indicates that the last bit of two strings is equal , So the longest common suffix has been added 1, namely dp[i][j] = dp[i - 1][j - 1] + 1;
When text1[i - 1] != text2[j - 1] when , The last bit of two substrings is not equal , At this time, the longest common suffix of the string is 0, namely dp[i][j] =0

dp[0][…] and dp[…][0] Represents that one of them is an empty string , The longest common suffix length is 0, Set the boundary conditions accordingly

If the last one is different , be dp[-1][-1]=0, But two strings may still have common substrings , So we need a variable to record the maximum value , instead of return dp[-1][-1]

class Solution(object):
    def findLength(self, nums1, nums2):
        """ :type nums1: List[int] :type nums2: List[int] :rtype: int """
        tot = 0
        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] = 0 
                tot = max(tot, dp[i][j])
        return tot 

Time complexity O(m Xn ), Spatial complexity O(m x n)