iven 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
Solution: DP
dp[i][j] := max length of (A[0:i], B[0:j])
dp[i][j] = dp[i – 1][j – 1] + 1 if A[i-1] == B[j-1] else 0
Time complexity: O(m*n)
Space complexity: O(m*n) -> O(n)
C++ S:O(mn)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua, 176 ms / 106.4 MB class Solution { public: int findLength(vector<int>& A, vector<int>& B) { int m = A.size(); int n = B.size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1)); int ans = 0; for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) if (A[i - 1] == B[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; ans = max(ans, dp[i][j]); } return ans; } }; |
C++ S:O(min(m,n))
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua, 152 ms / 9.1 MB class Solution { public: int findLength(vector<int>& A, vector<int>& B) { if (A.size() < B.size()) swap(A, B); int m = A.size(); int n = B.size(); vector<int> dp(n + 1); int ans = 0; for (int i = 1; i <= m; ++i) for (int j = n; j >= 1; --j) { dp[j] = A[i - 1] == B[j - 1] ? dp[j - 1] + 1 : 0; ans = max(ans, dp[j]); } return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment