当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.718.Maximum Length of Repeated Subarray 最长公共子串/最长重复子数组

LeetCode.718.Maximum Length of Repeated Subarray 最长公共子串/最长重复子数组

题目描述

718 Maximum Length of Repeated Subarray
https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/

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

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


相似题目

LeetCode.1143.Longest Common Subsequence 最长公共子序列LCS
LeetCode.718.Maximum Length of Repeated Subarray 最长公共子串/最长重复子数组
LeetCode.300.Longest Increasing Subsequence 最长上升子序列LIS


解题过程

注意区分 最长公共子序列 Longest Common Substring 和 最长公共子串 Longest Common Subsequence,子序列 Subsequence 不要求连续,子串 Substring 必须是连续的。

动态规划

lcs[i,j] 是序列 Xi=<x1, x2, …, xi>Yj=<y1, y2, …, yj> 的以 xi 和 yj 为结尾的(即必须包含xi和yj)最长公共子串的长度。
由于子串要求必须是连续的,其实也就是 xi,…,xm 和 yj,…,yn 的最长公共前缀
所以,当 xi 和 yj 相等时,就能和前面的接上,以 xi 和 yj 为结尾的最长公共子串就是以 xi-1 和 yj-1 为结尾的最长公共子串的长度加1
当 xi 和 yj 不等时,以 xi 和 yj 为结尾的最长公共子串的长度就是0
对比
LeetCode.053.Maximum Subarray 最大连续子序列和
题,可以发现,当遇到连续子序列时,递推公式中一定是以xx为结尾的,因为只有这样才能和前面连续的接上
或者可以这样对比子串和子序列:
由于子序列不连续,所以 dp[i][j] 可以从 dp[i-1][j] 或 dp[i][j-1] 转移过来,
由于子串必须连续,所以 dp[i][j] 只能从 dp[i-1][j-1] 转移。
而且,
子序列问题中,由于可以不连续,lcs[m][n] 就是最终结果。
但子串问题中,最终的结果并不是 lcs[m][n] ,而需要在递推的过程中不断更新最大值,也就是 lcs[0…m][0…n] 的最大值

所以

$
lcs[i,j] =
\begin{cases}
0, & \text{if $i = 0$ or $j = 0$ or $x_i \neq y_j$ } \\
cls[i-1, j-1] + 1, & \text{if $i,j > 0$ and $x_i = y_j$ } \\
\end{cases}
$

时间复杂度 O(mn),空间复杂度 O(mn)

private static class SolutionV2020 {
    public int findLength(int[] A, int[] B) {
        if (null == A || A.length == 0 || null == B || B.length == 0) {
           return 0;
        }
        // lcs[i][j] 表示 text1[0...i-1] 和 text2[0...j-1] 的以 text1[i-1],text2[j-1] 为结尾(必须包含)的最长公共子串的长度
        int[][] lcs = new int[A.length + 1][B.length + 1];
        // lcsStr[i][j] 表示 text1[0...i-1] 和 text2[0...j-1] 的以 text1[i-1],text2[j-1] 为结尾(必须包含)的最长公共子串
        String[][] lcsStr = new String[A.length + 1][B.length + 1];
        // A,B的最长公共子串长度
        int lcsMax = 0;
        // A,B的最长公共子串
        String lcsStrMax = "";

        for (int i = 0; i <= A.length; i++) {
            for (int j = 0; j <= B.length; j++) {
                if (i ==0 || j== 0) {
                    lcs[i][j] = 0;
                    lcsStr[i][j] = "";
                    continue;
                }
                if (A[i-1] == B[j-1]) {
                    lcs[i][j] = lcs[i - 1][j - 1] + 1;
                    lcsStr[i][j] = lcsStr[i - 1][j - 1] + A[i-1];
                    // 递推过程中要不断更新当前最大值
                    if (lcs[i][j] > lcsMax) {
                        lcsMax = lcs[i][j];
                        lcsStrMax = lcsStr[i][j];
                    }
                } else {
                    lcs[i][j] = 0;
                    lcsStr[i][j] = "";
                }
            }
        }
        System.out.println(lcsStrMax);
        return lcsMax;
    }
}

滑动窗口

将字符串s1和s2分别写在两把直尺上面,然后将s1固定,s2的尾部和s1的头部对齐,然后逐渐向右移动直尺s2,比较重叠部分的字符串中的公共子串的长度,直到直尺s2的头部移动到s1的尾部。在这个过程中求得的最大长度就是s1、s2最大子串的长度。


滑动窗口法

图片来自
https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/solution/wu-li-jie-fa-by-stg-2/

程序员面试100题之七:最长公共子字符串
https://blog.csdn.net/hackbuteer1/article/details/6686931


GitHub代码

algorithms/leetcode/leetcode/_718_MaximumLengthOfRepeatedSubarray.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_718_MaximumLengthOfRepeatedSubarray.java


上一篇 LeetCode.347.Top K Frequent Elements 前K个高频元素

下一篇 LeetCode.1143.Longest Common Subsequence 最长公共子序列LCS

阅读
评论
991
阅读预计5分钟
创建日期 2020-02-23
修改日期 2020-07-01
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论