Share accepted C++ code with O(n^2) time and O(1) space


  • 1
    J

    Suppose M=s.size() is the size of the string, for each character s[i], we need at most min(i,M-i) steps to find out the start and end locations of the longest palindrome centered at s[i]; and another at most min(i,M-i) steps to find out the start and end locations of the longest palindrome centered between s[i-1] and s[i]. All together, we need at most: 4*(1+2+...+M/2)=M^2/2+1, thus O(n^2) time. Only six size_t variables are used to store the start and end locations of the longest palindrome, current testing palindrome and a fake palindrome, thus O(1) for space.

    class Solution{
    public:
        string longestPalindrome(const string& s){
            if(s.empty())
                return string();
            const size_t strSize=s.size();
            const size_t maxIdx = strSize-1;
    
            //res_i0 and res_i1 are the start location
            //and end location of the longest palindrome substring
            //in s.
            size_t res_i0=0,res_i1=0;
    
            for(size_t i=1; i<strSize; ++i){
                //start from s[1], since s[0] has already been stored
                //by res_i0 and res_i1
    
                for(size_t offset = 0; offset<2; offset++){
                    //offset = 0: this palindrome centers on s[i]
                    //offset = 1: this palindrome center between s[i-1] and s[i]
                    //word_i0 and word_i1 are the start and end location of
                    //current palindrome
                    size_t word_i0 = i-offset;
                    bool end_of_pal = (s[word_i0]!=s[i]);
                    size_t word_i1 = end_of_pal?word_i0:i;
    
                    //p0 and p1 is the expanded start and end location of
                    //current palindrome
                    size_t p0=word_i0,p1=word_i1;
                    while(!end_of_pal)
                    {
                        word_i0=p0;     //execute palindrome range expansion
                        word_i1=p1;     //execute palindrome range expansion
                        p0=word_i0-1;   //prepare for next expansion
                        p1=word_i1+1;   //prepare for next expansion
                        end_of_pal = (word_i0<=0) || (word_i1>=maxIdx);     //determine whether expasion is possible (note that unsigned integer word_i0 is not possible to be reduced to -1, thus we have to check the possibility of expansion here
                        if(!end_of_pal)
                            end_of_pal=(s[p0]!=s[p1]);      //determine whether the expanded substring is still a palindrome
                    }
                    if(word_i1-word_i0>res_i1-res_i0)
                    {
                        //compare current palindrome substring length with the length of the longest one
                        res_i0=word_i0;
                        res_i1=word_i1;
                    }
                }
            }
            return s.substr(res_i0,res_i1-res_i0+1);
        }
    };

Log in to reply
 

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