Why my two O(n^2) methods have big difference in running time?


  • 0
    U
    string longestPalindrome(string s) {
        int n = s.size();
        int maxLen = 0, start = -1;
        bool dp[n][n];
        memset(dp, false, sizeof(dp));
        for(int i = n - 1; i >= 0; --i){
            for(int j = i; j < n; ++j){
                dp[i][j] = s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1]);
                if(dp[i][j]){
                    if(j - i + 1 > maxLen){
                        maxLen = j - i + 1;
                        start = i;    
                    }    
                }   
            }  
        } 
        return s.substr(start, maxLen);}                                                                                                    
    
     string longestPalindrome(string s) {
       int n = s.size();  
        if(n <= 1)  
            return s;  
        //n >= 2  
        int maxLen = 1;  
        int maxStart = 0;  
        for(int i = 1; i < n; ++i){  
            //find the longest even palindrome around i  
            int low = i - 1;  
            int high = i;  
            while(low >= 0 && high < n && s[low] == s[high]){  
                if(high - low + 1 > maxLen){  
                    maxLen = high - low + 1;  
                    maxStart = low;  
                }  
                low--;  
                high++;           
            }  
            //find the longest odd palindrome around i  
            low = i - 1;  
            high = i + 1;  
            while(low >= 0 && high < n && s[low] == s[high]){  
                if(high - low + 1 > maxLen){  
                    maxLen = high - low + 1;  
                    maxStart = low;  
                }  
                low--;  
                high++;           
            }  
        }  
        return s.substr(maxStart, maxLen);        
    }
    

    The first one is dp - 228 ms. The second one is "search twice" - 68 ms. Why there is such a big difference? Where I've done wrong?


  • 0
    I

    Your second solution will work better when the average palindrome size is small.

    In some cases, e.g. "aaaa...aaaa" the solutions will probably have similar runtime,
    but for if the input string is "abcabcabc..." the other solution will work in linear time.


Log in to reply
 

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