Why my O(n^2) dp solution got "aaaaaa...a" TLE?


  • 6
    S
    string longestPalindrome(string s) {
        if (s.size() == 0) {
            return "";
        }
        
        int n = (int)s.size();
        
        vector<vector<bool>> isPP (n, vector<bool> (n, false));
        for (int i = 0; i < n; i++) {
            isPP[i][i] = true;
        }
        
        int maxLen = 1;
        int start = n - 1;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s[i] == s[j] && (j - i <= 2 || isPP[i + 1][j - 1])) {
                    isPP[i][j] = true;
                    maxLen = max(maxLen, j - i + 1);
                    start = i;
                }
            }
        }
        
        return s.substr(start, maxLen);
    }

  • 0
    S

    Questions about code you've written must describe the specific problem clearly, elaborate thoughts based on code and preserve code formatting as well. Please read the FAQ for more info.


  • 8
    Y

    simply using vector is tooooo slow........ I've changed your code to the following:

    //vector<vector<bool>> isPP (n, vector<bool> (n, false));
    
    bool isPP[1100][1100];
    memset(isPP,false,sizeof(isPP));
    

    no TLE,,,, but Wrong Answer... maybe there are some bugs in your program.


  • 1
    W

    the variable "start" should only be updated when a larger length is found (j-i+1>maxLen).

    Another DP approach is to remember length and start position instead of start and end positions. Such an arrangement allows a possible speedup. E.g., if we know there is no palindromic substring of length 3, it is then impossible to find any substring of length 5,7,etc. So we may stop earlier. Here is the sample code:

    class Solution {
    public:
        string longestPalindrome(string s) {
            int n=s.size();
            if(n==0) return "";
            if(n==1) return s;
            bool book[1005][1005];
            memset(book,0,sizeof(book));
            int valid_len=1,pos=0;
            bool chk[2]={true,true};
            for(int i=0;i<n;i++) book[1][i]=1;
            for(int i=0;i<n-1;i++) { 
                book[2][i]=s[i]==s[i+1]?1:0; 
                if(book[2][i]) {
                    valid_len=2;
                    pos=i;
                }
            }
            for(int len=3;len<=n;len++) {
                bool found=false;
                if(!chk[0] && !chk[1]) break;
                if(!chk[len%2]) continue;
                for(int l=0;l+len<=n;l++) {
                    int r=l+len-1;
                    book[len][l]=s[l]==s[r]&&book[len-2][l+1];
                    if(book[len][l]) {
                        found=true;
                        valid_len=len;
                        pos=l;
                    }
                }
                if(!found) {
                    chk[len%2]=false;
                }
            }
            return s.substr(pos,valid_len);
        }
    };

  • 0
    A

    i think your code will always do n-square iterations...
    maybe a possible optimization is:
    try to find a palindrome of length len = s.length(), then len-1, len-2...
    whenever it's found, return immediately as this is the longest one, and you don't need to check the remaining.
    i think the worse case comlexity is still the same.


  • 0
    S

    Your code is wrong. A correct version is as below.

        class Solution {
        public:
            string longestPalindrome(string s) {
        		if (s == "") return s; 
        		unsigned size = s.size(); 
        
        		bool table[1100][1100];
        		memset(table,false,sizeof(table));
        
        /*	
                        // too slow when using vector
        	        vector <vector <bool> > table (size) ; 
        		for (unsigned i = 0; i < size; ++i)
        			table[i] = vector <bool> (size, false) ; */
        
        		for (unsigned i = 0; i < size; ++i)
        			table[i][i] = true; 
        
        		int maxlength = 1; 
        		int start = size - 1 ; 
        		for (int i = size - 1; i >= 0; --i )
        		{
        			for (int j = i ; j < size; ++j)
        			{
        				if (s[i] == s[j] && (j - i <= 2 || table[i+1][j-1]))
        				{
        					table [i][j] = true; 
    // Fixed the error here. 
        					if (maxlength < j - i + 1)
        					{
        						maxlength = j - i + 1; 
        						start = i; 
        					}
        				}
        			}
        		}
        		return s.substr (start, maxlength) ; 
            }
        };
    

  • 0
    E

    My AC code, after change vector to array.

    class Solution {
    public:
    string longestPalindrome(string s) {
    int len = s.size();
    int dp[len][len];
    int maxl = 1;
    int l = 0;
    for(int i = len - 1; i >= 0; --i) {
    for(int j = i; j < len; ++j) {
    dp[i][j] = false;
    if(s[i] == s[j] && (j-i <= 2 || dp[i+1][j-1])) {
    dp[i][j] = true;
    if(j-i+1 > maxl) {
    l = i;
    maxl = j-i+1;
    }
    }
    }
    }

        return s.substr(l, maxl);
    }
    

    };


  • 0

    Here is the AC version, I recommend you to set the size of the DP array to be (n + 1)

    class Solution {
    public:
        string longestPalindrome(string s) {
            int n  = s.size();
            if(n == 0)  return s;
            
            bool dp[1001][1001] ;
            //vector<vector<bool>> dp(n + 1, vector<bool>(n + 1, false));
            for(int i = 0; i <= n; i++) dp[i][i] = true;
            
            int max_len = 1;
            string str_res = s.substr(0, 1);
            for(int i = n - 1; i > 0; i--) {
                for(int j = i + 1; j <= n; j++) {
                    if(j == (i + 1)) {
                        dp[i][j] = (s[i-1] == s[j-1]);
                    } else {
                        dp[i][j] = (s[i-1] == s[j-1]) && dp[i+1][j-1];
                    } 
                    if(dp[i][j] && ((j - i + 1) > max_len)) {
                        max_len = j - i + 1;
                        str_res = s.substr(i - 1, max_len);
                    }
                }
            }
            return str_res;
        }
    };

Log in to reply
 

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