Leetcode: Maximum Length of Repeated Subarray

// Blog link: https://code.dennyzhang.com/maximum-length-of-repeated-subarray
// Basic Ideas: dynamic programming
//
//   Let's say the common subarray starts with A[i] and B[j]
//   If A[i] == B[j], then dp[i][j] = dp[i]
//   Otherwise dp[i][j] = 0
//  So from right to left, we get dp[][]
//  Then find the maximum
//
// To save the code of base case, we add an extra line and column
//
// Complexity: Time O(n*m), Space O(n*m)
func findLength(A []int, B []int) int {
    len_a, len_b := len(A), len(B)
    dp := make([][]int, len_a+1)
    for i:=0; i<len_a+1; i++ { dp[i] = make([]int, len_b+1) }
    // A: [1,2,3,2,1]
    // B: [3,2,1,4]
    res := 0
    // dp
    for i := len_a-1; i>=0; i-- {
        for j := len_b-1; j>=0; j-- {
            if A[i] == B[j] {
                dp[i][j] = dp[i+1][j+1] + 1
                if dp[i][j] > res { res = dp[i][j]}
            }
        }
    }
    return res
}

• – Solution2: dp: Time O(n*m), Space O(n+m)

// Blog link: https://code.dennyzhang.com/maximum-length-of-repeated-subarray
//
// From right to left
//
// dp[i][j] only depend on dp[i+1][j+1].
// So Instead of 2D array, we use 2 1D array
//
// Complexity: Time O(n*m), Space O(m)
func findLength(A []int, B []int) int {
    len_a, len_b := len(A), len(B)
    dp := make([]int, len_b+1)
    // A: [1,2,3,2,1]
    // B: [3,2,1,4]
    res := 0
    // dp
    for i := len_a-1; i>=0; i-- {
        dp2 := make([]int, len(dp))
        copy(dp2, dp)
        for j := len_b-1; j>=0; j-- {
            if A[i] == B[j] {
                dp2[j] = dp[j+1] + 1
                if dp2[j]> res { res = dp2[j] }
            }
        }
        copy(dp, dp2)
    }
    return res
}