O(N^2) solution with no extra space. C++. Divide the solution into two cases. Any improvement?


  • 1
    G

    Similar to the idea at the bottom of this leetcode page, we divide the solution into two cases:

    (1) palindromic substring with one letter as the middle point

    (2) palindromic substring with the center between two letters as the middle point

    class Solution {
    public:
        string longestPalindrome(string s) {
            if (s.size()==0)
                return "";
            
            // Base case: there is just one letter in the string
            int maxLength= 1 ;
            string result=s.substr(0,1);
            
            for (int i =0; i<s.size()-1; i++) {
                // substring with the letter as the middle point
                int count = 0;
                while (i-count>=0 && i+count<=s.size()-1) {
                    if (s[i-count]==s[i+count])
                        count++;
                    else
                        break;
                }
                count--;
                if (count*2+1>=maxLength) {
                    maxLength = count*2+1;
                    result = s.substr(i-count,count*2+1);
                }
                
                // substring with the center between two letters as the middle point
                int count2 = 0;
                while (i-count2>=0 && i+count2+1<=s.size()-1) {
                    if(s[i-count2]==s[i+1+count2])
                        count2++;
                    else
                        break;
                }
                if(count2*2>=maxLength) {
                    maxLength = count2*2;
                    result = s.substr(i+1-count2, count2*2);
                }
            }
            return result;
            
        }
    };
    

  • 0
    G

    There is a Manacher's algorithm, it's a linear time algorithm


Log in to reply
 

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