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;
}