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 = *(N+1), *(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