LeetCode718 最长连续子串

2018-04-19  本文已影响0人  codingcyx

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

解法一(基础dp):

int findLength(vector<int>& A, vector<int>& B) {
        int n = A.size(), m = B.size();
        int res = 0;
        vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
        for(int i = 0; i<n+1; i++){
            for(int j = 0; j<m+1; j++){
                if(i == 0 || j == 0)
                    dp[i][j] = 0;
                else if(A[i-1] == B[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    res = max(res, dp[i][j]);
                }
                else dp[i][j] = 0;
            }
        }
        return res;
    }

dp[i][j]代表以A[i-1]和B[j-1]结尾的最长连续子串。

解法二(对角线遍历):

int findLength(vector<int>& A, vector<int>& B) {
        //traverse diagonally
        int n = A.size(), m = B.size();
        int res = 0;
        for(int j = 0; j<m; j++){
            int rec = 0;
            for(int i = 0, k = j; i<n && k<m; i++, k++) {
                if(A[i] == B[k]){
                    rec++;
                    res = max(res, rec);
                }
                else rec = 0;
            }
        }
        for(int i = 0; i<n; i++){
            int rec = 0;
            for(int j = 0, k = i; k<n && j<m; j++, k++) {
                if(A[k] == B[j]){
                    rec++;
                    res = max(res, rec);
                }
                else rec = 0;
            }
        }
        return res;
    }
上一篇 下一篇

猜你喜欢

热点阅读