C++, Easy solution with explanation


  • 1
    Z

    The idea is to shift one of the arrays left by k position (0 <= k < n), and to find the longest common sub-array in each case. The run time is O(mn).
    For example,

    shift array A left by 2 positions, max length is helper(A, B, 2, 0)
    A: 3 5 1 2 3 4 6 2
    B:     1 2 3 4 5 4
    
    class Solution {
    public:
        int findLength(vector<int>& A, vector<int>& B) {
            int ans = 0, m = A.size(), n = B.size();
            for (int i = 0; i < m; i++) 
                ans = max(ans, helper(A, B, i, 0));
            for (int j = 1; j < n; j++) 
                ans = max(ans, helper(A, B, 0, j));
            return ans;
        }
    private:
        int helper(vector<int>& A, vector<int>& B, int i, int j) {
            int len = 0, cnt = 0;
            for (;i < A.size() && j < B.size(); i++, j++) {
                if (A[i] == B[j]) 
                    len = max(len, ++cnt);
                else 
                    cnt = 0;
            }
            return len;
        }
    };
    

Log in to reply
 

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