Leetcode | Maximum Length of Repeated Subarray

发表于   |   分类于   |     |   阅读次数

718. 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:

1
2
3
4
5
6
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

! subarray, not subsequence

  • I. DP,
  1. Similar to LCS
  2. Time Complexity: O($L_A$x $L_B$)
  3. Space Complexity: O($L_A$x $L_B$)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//c++
class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
    	int l = A.size(),ans = 0;
    	vector<vector<int>> dp(l,vector<int>(l,0));
    	for (int i=0;i<l;i++){
    		for (int j=0;j<l;j++){
    			if(i == 0 || j == 0) dp[i][j] = (A[i]==B[j]);
    			else dp[i][j] = (A[i]==B[j]) ? dp[i-1][j-1]+1:0;
    			ans = max(ans,dp[i][j]);
    		}
    	}
    	return ans;
    }
};
  • II. Optimization
  1. DP
  2. Time Complexity: O($L_A$x $L_B$)
  3. Space Complexity: O($L_A$)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//c++
class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        int m = A.size();
        int n = B.size();
        vector<int> dp(n + 1);
        int result = 0;
        for (int i = 1; i <= m; ++i) {
            vector<int> ndp(n + 1);
            for (int j = 1; j <= n; ++j) {
                if (A[i-1] == B[j-1]) {
                    ndp[j] = dp[j-1] + 1;
                    result = max(ndp[j], result);
                }
            }
            dp = ndp;
        }
        return result;
    }
};
  • III. Optimization 2
  1. DP
  2. Time Complexity: O($L_A$x $L_B$)
  3. Space Complexity: O(1)
    since dp[i][j] only depends on dp[i-1][j-1], we only need to keep it and traverse the matrix diagonally.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//Java
public int findLength(int[] A, int[] B) {
        int maxLen = 0;      
        for (int j = 0; j < B.length; j++) {
            int maxLenEnding = 0;
            for (int i = 0, k = j; i < A.length && k < B.length; i++, k++) {
                if (A[i] != B[k]) maxLenEnding = 0;
                else {
                    maxLenEnding++;
                    maxLen = Math.max(maxLen, maxLenEnding);
                }
            }
        }
        
        for (int i =1; i < A.length; i++) {
            int maxLenEnding = 0;
            for (int j = 0, k = i; k < A.length && j < B.length; j++, k++) {
                if (A[k] != B[j]) maxLenEnding = 0;
                else {
                    maxLenEnding++;
                    maxLen = Math.max(maxLen, maxLenEnding);
                }
            }
        }
        return maxLen;  
    }
  • IV. HashMap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
//c++
struct Node {
  int len;
  Node *ch[101], *f;
  Node() : len(0), f(NULL) { memset(ch, 0, sizeof ch); }
};
struct SAM {
  Node *last, *root;
  SAM() { root = last = new Node(); };
  void add(int c) {
    Node *e = new Node(), *tmp = last;
    e->len = last->len + 1;
    for (; tmp && !tmp->ch[c]; tmp = tmp->f)
      tmp->ch[c] = e;
    if (!tmp) {
      e->f = root;
    } else {
      Node *nxt = tmp->ch[c];
      if (tmp->len + 1 == nxt->len)
        e->f = nxt;
      else {
        Node *np = new Node();
        *np = *nxt;
        np->len = tmp->len + 1;
        nxt->f = e->f = np;
        for (; tmp && tmp->ch[c] == nxt; tmp = tmp->f)
          tmp->ch[c] = np;
      }
    }
    last = e;
  }
};

class Solution {
public:
  int findLength(vector<int> &A, vector<int> &B) {
    SAM a = SAM();
    for (int x : A) a.add(x);
    int ans = 0, cur = 0;
    Node *t = a.root;
    for (int i = 0; i < B.size() && t; ++i) {
      int idx = B[i];
      while (t != a.root && !t->ch[idx]) {
        t = t->f;
        cur = t->len;
      }
      if (t->ch[idx]) {
        t = t->ch[idx];
        cur++;
      }
      if (cur > ans)
        ans = cur;
    }
    return ans;
  }
};

相关题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int numDistinct(string s, string t) {
    	int l1 = s.length(), l2 = t.length(), tmp, pre;
    	vector<int> dp(l2+1,0);
    	dp[0] = 1;
    	for (int i=1;i<=l1;i++){
    		pre = 1;
    		for (int j=1;j<=l2;j++){
    			tmp = dp[j];
    			dp[j] = dp[j] + (s[i-1]==t[j-1] ? pre:0);
    			pre = tmp;
    		}
    		cout << endl;
    	}
    	return dp[l2];
    }
};