718. Maximum Length of Repeated Subarray

https://leetcode.com/problems/maximum-length-of-repeated-subarray/

Maximum Length of Repeated Subarray - LeetCode

 

class Solution {
public:
    int getSubLength(vector<int>& nums1, vector<int>& nums2, int i, int j){
        int ret = 0;
        while(i < nums1.size() && j < nums2.size()){
            if(nums1[i] != nums2[j]){
                break;
            }
            ret++;
            i++;
            j++;
        }
        return ret;
    }
    
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, vector<int>> idxs;
        
        for(int i = 0; i < nums2.size(); i++){
            int v = nums2[i];
            idxs[v].push_back(i);
        }
        
        int ans = 0;
        
        for(int i = 0; i < nums1.size(); i++){
            int v = nums1[i];
            for(auto j : idxs[v]){
                ans = max(ans, getSubLength(nums1, nums2, i, j));
            }
        }
        return ans;
    }
};

 unordered_map에 index만 집어넣고 이중루프 돌면서 sublength를 반환한다.  겹치는 글자가 너무 많은경우에 취약하다.  

 

1 <= nums1.length, nums2.length <= 1000

 

 범위가 1000이면 모두 동일한 숫자가 들어있다고 가정할때 시간복잡도는 O(N^3)이 걸리고 이는 1초의 임계시간을 아득히 넘는다.  계산하면 1,000,000,000이다.  

 

 getSubLength할 때 앞에서 뒤로 밀기만해서 caching하기가 까다로움

 

class Solution {
public:
    int visited[1001][1001];
    int ans = 0;
    int getSubLength(vector<int>& nums1, vector<int>& nums2, int i, int j){
        if(i >= nums1.size() || j >= nums2.size()){
            return 0;
        }
        
        int & ret = visited[i][j];
        
        if(ret != -1){
            return ret;
        }
        ret = 0;
        
        if(nums1[i] == nums2[j]){
            ret = 1 + getSubLength(nums1, nums2, i + 1, j + 1);
        } 
        getSubLength(nums1, nums2, i, j + 1);
        getSubLength(nums1, nums2, i + 1, j);

        ans = max(ans, ret);
        return ret;
    }
    
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        memset(visited, -1, sizeof(visited));
        getSubLength(nums1, nums2, 0, 0);
        return ans;
    }
};

 1000 x 1000에서 한 번 방문했던 위치는 캐싱하므로 시간복잡도는 O(N^2)이 걸린다.

 

 

+  효율성 체크 필요

 

-효율체크

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int cache[1001][1001];
        memset(cache, -1, sizeof(cache));
        
        int ans = 0;
        
        for(int i = 0; i <= nums1.size(); i++){
            for(int j = 0; j <= nums2.size(); j++){
                if(i == 0 || j == 0){
                    cache[i][j] = 0;
                    continue;
                }
                
                if(nums1[i - 1] == nums2[j - 1]){
                    cache[i][j] = 1 + cache[i - 1][j - 1];
                } else {
                    cache[i][j] = 0;
                }
                ans = max(ans, cache[i][j]);
            }
        }
        return ans;
    }
};

 연속 sub array를 판별할 때 nums1과 nums2를 2차원 배열로 매핑하면 대각선이 같으냐 다르냐에 따라 연속인지 아닌지 판별할 수 있다.  즉, 이중루프를 돌면서 각 셀의 문자가 같은지 아닌지 판별하고 같으면 cache[i - 1][j - 1]과 더해줬을때 모든 sub array 경우의 수를 구할 수 있다.

 

 max(cache[i - 1][j - 1] + 1) if nums[i] == nums[j]

 

Time complexity: O(N^2)

Space complexity: O(N^2)

 

 

 recursion을 사용하는것과 시간복잡도는 동일하지만, recursion은 각 호출 시 stack frame을 사용하므로 이중루프를 도는것에 비해 상대적으로 비효율적이다.