MENU

LeetCode718. Maximum Length of Repeated Subarray(最长公共子串)

2019 年 04 月 09 日 • 阅读: 1120 • LeetCode阅读设置

LeetCode718. Maximum Length of Repeated Subarray(最长公共子串)

  • Medium
  • Accepted:30,475
  • Submissions:67,182

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. 1 <= len(A), len(B) <= 1000
  2. 0 <= A[i], B[i] < 100

链接

https://leetcode.com/problems/maximum-length-of-repeated-subarray

题意

给定两个整数数组,求最长公共子串。

题解

这题和最长公告子序列基本上差不多,一个不同的地方在于“子串要求连续”,因此当A[i]!=B[j]时,C[i][j]应该为0。

$c[i, j]=\left\{\begin{array}{cc}{0} & {i=0 \text { or } j=0} \\ {c[i-1, j-1]+1} & {x_{i}=y_{j}} \\ {0} & {x_{i} \neq y_{j}}\end{array}\right.$

时间复杂度$O(nm)$,空间复杂度$O(nm)$。

代码

Time SubmittedStatusRuntimeMemoryLanguage
2 days agoAccepted240 ms106.2 MBcpp
class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        int n = A.size(), m = B.size();
        vector <vector<int> > C(n + 1, vector<int>(m + 1, 0));
        int ans = 0;
        for (int i = 0; i <= n; ++i)
        {
            for (int j = 0; j <= m; ++j)
            {
                if (i == 0 || j == 0)
                    C[i][j] = 0;
                else if (A[i - 1] == B[j - 1])
                {
                    C[i][j]  = C[i - 1][j - 1] + 1;
                    ans = max(ans, C[i][j]);
                }
                else if (A[i - 1] != B[j - 1])
                    C[i][j] = 0;
            }
        }
        return ans;
    }
};

The end.
2019年4月9日 星期二、
最后编辑于: 2019 年 04 月 15 日