Leetcode 718.最长重复子数组

Posted on |

718. 最长重复子数组

题目

给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

1
2
3
4
5
6
7
8
示例 1:

输入:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出: 3
解释:
长度最长的公共子数组是 [3, 2, 1]。

说明:

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

方法

方法1：动态规划

dp[i]：表示字串A[0…i-1]和B[0…j-1]最长重合子数组的长度
需注意，这里要求的是连续的子数组，并不是最长公共子序列（可以是断开的）
状态转移方程dp[i+1][j+1]=dp[i]dp[j]+1 if A[i]==B[j]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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=[[0 for _ in range(n+1)] for _ in range(m+1)]

        for i in range(m):
            for j in range(n):
                if A[i]==B[j]:
                    dp[i+1][j+1]=dp[i][j]+1
        return max(max(row) for row in dp)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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=[[0 for _ in range(n+1)] for _ in range(m+1)]

        maxlen=0
        for i in range(1,m+1):
            for j in range(1,n+1):
                if A[i-1]==B[j-1]:
                    dp[i][j]=dp[i-1][j-1]+1
                    maxlen=max(maxlen,dp[i][j])
        return maxlen