Python solution with detailed explanation


  • 0
    G

    Maximum Length of Repeated Subarray https://leetcode.com/problems/maximum-length-of-repeated-subarray/description/

    Time O(N^2) and Space O(N) DP Solution

    • dp[i][j] indicates the maximum length of repeated subarray which ends at index i-1 in A and index j-1 in B i.e. index i-1 is length i when measured from the start of the array. This gives the recurrence dp[i][j] = dp[i-1][j-1] + 1 if A[i-1] == B[j-1] else 0.
    • While we can initialize a 2D matrix to compute this, we really need two vectors of dimension (N+1) since the dp[i][j] just depends on the previous row.
    class Solution(object):
        def findLength(self, A, B):
            """
            :type A: List[int]
            :type B: List[int]
            :rtype: int
            """
            M, N = len(A), len(B)
            dp, temp = [0]*(N+1), [0]*(N+1)
            ans = 0
            for i in range(1, M+1):
                for j in range(1, N+1):
                    dp[j] = temp[j-1] + 1 if A[i-1] == B[j-1] else 0
                ans = max(ans, max(dp))
                temp, dp = dp, temp
            return ans
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.