Can O(n^2) solution solve the large string within time limit?


  • 0
    L

    Hi, I have a O(n^2) solution. However, when the input string is:

    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabcaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    it returns time limit exceed. I know it is better to search from the mid point instead of searching from left end. But can this overcome the time limit issue? or we much use O(n) solution. Thanks.

    string longestPalindrome(string s) {

    int length = s.size();
    
    if (length == 0)
    {
    	return 0;
    }
    
    int cp = 1;
    
    int lp = cp - 1;
    int up = cp + 1;
    
    int max_len = 1;
    
    int output_len = 1;
    int output_cp = 1;
    
    map<int, int> recorder;
    
    while (cp <= length - 1)
    {
    
    	while (lp >= 0 && up < length)
    	{
    
    		if (s[lp] == s[up])
    		{
    			max_len += 2;
    			lp = lp - 1;
    			up = up + 1;
    			recorder[cp] = max_len;
    
    			if (max_len >= output_len)
    			{
    				output_len = max_len;
    				output_cp = cp;
    
    			}
    
    		}
    
    		else
    		{
    			break;
    		}
    
    	}
    
    
    	cp = cp + 1;
    	lp = cp - 1;
    	up = cp + 1;
    	max_len = 0;
    
    
    }
    
    
    string output_str = s.substr(output_cp - output_len / 2, output_cp + output_len / 2 + 1);
    
    
    return output_str;
    

    }


  • 1
    U
    string longestPalindrome(string s){
    int n = s.size();
    int maxLen = 0, start = 0;
    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);    
    

    }

    This is my dp method. It's obviously O(n^2). It passes the OJ.


Log in to reply
 

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