Accepted C++ solution using tabulation (DP) very readable code


  • 0
    W
    string longestPalindrome(string str)
    {
    	if (str.size() <= 1) return str;
    	
    	bool table[1000][1000];
    	memset(table, 0, 1000 * 1000 * sizeof(bool));
    	
    	int left = 0, right = 0;
    	for (int i = 0; i < str.size(); i++)
    	{
    		for (int j = 0; j <= i; j++)
    		{
    			if (i == j) 
    				table[i][j] = true;
    			else if (i - 1 == j)
    				table[i][j] = str.at(i) == str.at(j);
    			else
    				table[i][j] = table[i-1][j+1] && str.at(i) == str.at(j);
    			
    			if (table[i][j] && i - j > right - left)
    			{
    				left = j;
    				right = i;
    			}
    		}
    	}
    	
    	return str.substr(left, right - left + 1);
    }

  • 0
    H

    the running time is: 1 + 2 + ... + n = n(n+1)/2, which is O(n^2)


  • 0
    W

    yeap--------


Log in to reply
 

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