718. Maximum Length of Repeated Subarray

发表于 | 分类于 | |

718. Maximum Length of Repeated Subarray

题目描述

Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.

1
2
3
4
5
6
7
Example 1:
Input:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
Output: 3
Explanation: 
The repeated subarray with maximum length is [3, 2, 1].

Note:
1 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100

题目大意

求两个数组内的最长重复子数组。

解题思路

动态规划
遍历数组，找到A和B中数值相等的下标，分别记为i和j，则需将dp[i][j]置为1，如果i + 1和j + 1数值也相同，则此时dp[i+1][j+1]的值应为2。
故有动态规划方程式dp[i + 1][j + 1] = dp[i][j] + 1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    func findLength(_ A: [Int], _ B: [Int]) -> Int {
        var dp = Array(repeating: Array(repeating: 0, count: B.count + 1), count: A.count + 1)
        var ans = 0
        for i in 0..<A.count {
            for j in 0..<B.count {
                if A[i] == B[j] {
                    dp[i + 1][j + 1] = dp[i][j] + 1
                    ans = max(ans, dp[i + 1][j + 1])
                }
            }
        }
        return ans
    }
}
0%