Why algorithm with O(N^3 * logN) time compexity can be accepted?


  • 0
    F
    class Solution {
    public:
        bool test(vector<int>& A, vector<int>& B, int mid){
            int asz = A.size(), bsz = B.size();
            for(int i = 0;i <= asz - mid;++i){
                for(int j = 0;j <= bsz - mid;++j){
                    bool ans = true;
                    for(int k = 0;k < mid;++k){
                        if(A[i + k] != B[j + k]){
                            ans = false;
                            break;
                        }
                    }
                    if(ans)return true;
                }
            }
            return false;
        }
        int findLength(vector<int>& A, vector<int>& B) {
            int low = -1, high = 1010, mid;
            while(low < high - 1){
                mid = (low + high) / 2;
                if(test(A, B, mid))low = mid;
                else high = mid;
            }
            return low;
        }
    };
    

Log in to reply
 

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