Maximum Length of Repeated Subarray


  • 0

    Click here to see the full article post


  • 2

    The Python version of approach #2 doesn't get me "Time Limit Exceeded" but "Memory Limit Exceeded". I think it's fairly fast. I changed it to use strings, now it doesn't get MLE anymore. And it gets accepted in about 140 ms, which is faster than approaches #3 and #4 (which take about 2800 ms and 170 ms 250 ms[*], respectively):

    def findLength(self, A, B):
        def check(length):
            seen = {A[i:i+length]
                    for i in xrange(len(A) - length + 1)}
            return any(B[j:j+length] in seen
                       for j in xrange(len(B) - length + 1))
    
        A = ''.join(map(chr, A))
        B = ''.join(map(chr, B))
        lo, hi = 0, min(len(A), len(B)) + 1
        while lo < hi:
            mi = (lo + hi) / 2
            if check(mi):
                lo = mi + 1
            else:
                hi = mi
        return lo - 1
    

    [*] The bug fix discussed below made it slower.


  • 0
    A

    The implementation of Approach has some bug if there are two subarrays having the same hash value. In order to make the code 100% correct, we should define hashes as Map<Integer, List<Integer>>.

        for (int x: rolling(A, guess)) {
            hashes.put(x, i++); // this has bug, should be something like hashes.put(x, new ArrayList<Integer>().add(i++);
        }
    

    ===========


  • 0

    @amazontiger01 Good catch, I corrected it.


  • 0
    S

    I think O(1) space is enough for this problem :

    see below post:
    https://discuss.leetcode.com/topic/109751/java-o-mn-time-o-1-space


  • 0
    Q

    This solution is O(M*N) in time, and O(min(M,N)) in space. It takes advantage of the fact that we don't need to rebuild the sequence when we're done, we only need to know the length. We also know that as we introduce new characters, we dont need to worry about results too far in the past, only the lengths of subarrays we found from the previous character:

    class Solution {
    public:
        int findLength(vector<int>& A, vector<int>& B) {
            
            if(A.empty() || B.empty()) {
                return 0;
            }
            
            vector<int>* longer  = &A;
            vector<int>* shorter = &B;
            
            if(A.size() < B.size()){
                longer = &B;
                shorter = &A;
            }
            
            vector<short> dpt(shorter->size() + 1, 0);
            short * dp = &dpt[1];
            
            short len = 0;
                    
            for (const int v : *longer) {
                for (short i = shorter->size() - 1; i >= 0 && len < shorter->size(); --i) {
                    if(v == (*shorter)[i]) {
                        dp[i] = dp[i - 1] + 1;
                        
                        if(dp[i] > len) {
                            len = dp[i];
                        }
                    }
                    else {
                        dp[i] = 0;
                    }
                }
            }
            return len;
        }
    };
    

  • 0
    A

    @StefanPochmann , for approach #2, by following the same in Java gets me accepted too . It looks like it may not work if this prerequisite is removed : 0 <= A[i], B[i] < 100 i.e. if any value is greater than 255.


  • 0
    C

    I am confused. If Let dp[i][j] be the answer to the problem for inputs A[i:] and B[j:], why the answer is not dp[0][0]?


  • 0
    Z

    @Chengcheng.Pei .Once you get a A[i] != B[j], the corresponding dp[i][j] will be 0(initialized) , then we start from 0 again.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.