LeetCode 718 最长重复子数组 题解

LeetCode 718 最长重复子数组 题解

给两个整数数组 A 和 B ,返回两个数组中公共的、长度最长的子数组的长度。
示例:
输入:
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

参考题解

A 、B数组各抽出一个子数组,单看它们的末尾项,如果它们俩不一样——以它们俩为末尾项形成的公共子数组的长度为0:dp[i][j] = 0
如果它们俩一样,以它们俩为末尾项的公共子数组,长度保底为1——dp[i][j]至少为 1,要考虑它们俩的前缀数组——dp[i-1][j-1]能为它们俩提供多大的公共长度
如果它们俩的前缀数组的「末尾项」不相同,前缀数组提供的公共长度为 0——dp[i-1][j-1] = 0
以它们俩为末尾项的公共子数组的长度——dp[i][j] = 1
如果它们俩的前缀数组的「末尾项」相同
前缀部分能提供的公共长度——dp[i-1][j-1],它至少为 1
以它们俩为末尾项的公共子数组的长度 dp[i][j] = dp[i-1][j-1] + 1
题目求: 最长公共子数组的长度。不同的公共子数组的末尾项不一样。我们考察不同末尾项的公共子数组,找出最长的那个。(注意下图的最下方的一句话)
LeetCode 718 最长重复子数组 题解

状态转移方程

dp[i][j] :长度为i,末尾项为A[i-1]的子数组,与长度为j,末尾项为B[j-1]的子数组,
二者的最大公共后缀子数组长度。
如果 A[i-1] != B[j-1], 有 dp[i][j] = 0
如果 A[i-1] == B[j-1] , 有 dp[i][j] = dp[i-1][j-1] + 1
base case:如果i==0||j==0,则二者没有公共部分,dp[i][j]=0
最长公共子数组以哪一项为末尾项都有可能,求出每个 dp[i][j],找出最大值。

LeetCode 718 最长重复子数组 题解

代码

class Solution {
    public int findLength(int[] A, int[] B) {
        int lenA = A.length, lenB = B.length;
        int[][] dp = new int[lenA+1][lenB+1];
        int res = 0;
        for(int i = 1; i <= lenA; i++){
            for(int j = 1; j <= lenB; j++){
                if(A[i-1] == B[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                //A[i-1] != B[j-1]的话,dp[i][j] = 0,一开始就默认为0
                res = Math.max(dp[i][j], res);
            }
        }
        return res;
    }
}

时间复杂度 O(n * m)O(n∗m)。 空间复杂度 O(n * m)O(n∗m)。
降维后空间复杂度 O(n)O(n),如果没有空间复杂度的要求,降不降都行。

降维优化

dp[i][j] 只依赖上一行上一列的对角线的值,所以我们从右上角开始计算。
一维数组 dp , dp[j] 是以 A[i-1], B[j-1] 为末尾项的最长公共子数组的长度

LeetCode 718 最长重复子数组 题解

代码:

 int[] dp = new int[lenB+1];
        int res = 0;
        for(int i = 1; i <= lenA; i++){
            for(int j = lenB; j >= 1; j--){
                if(A[i-1] == B[j-1]){
                    dp[j] = dp[j-1] + 1;
                }else{
                    dp[j] = 0;//一定要加上这一句
                }
                res = Math.max(dp[j], res);
            }
        }
        return res;
上一篇:LeetCode 718. 最长重复子数组(DP)


下一篇:JAVA 构建器内部的多形性方法的行为