My Solution Is Naive, It Cost O(n^2), Is there Any Solution faster?


  • 6
    N

    My Solution Is Naive, It Cost O(n^2), Is there Any Solution faster?


  • 21

    There is an O(n) algorithm called Manacher's algorithm, explained here in detail. However, it is a non-trivial algorithm, and no one expects you to come up with this algorithm in a 30 minutes coding session. But, please go ahead and understand it, I promise it will be a lot of fun.


  • 0
    P

    This is efficient yet beautiful solution. I love it =)


  • 2
    R

    it'd be more helpful if you described your solution instead of just saying "naive"
    however, the trivial solution is N^3, not N^2. So yours is probably N^3


  • 0
    R

    I think it's n^2. for each character, you scan at most the whole string onece


  • 9
    V

    The trivial solution refers to the brute force method which has o(n^3) cost and o(1) auxiliary space.
    One can improve upon time complexity by applying Dynamic programming technique thus reducing the time complexity to o(n^2), but on the down side the DP algo has auxiliary space complexity of o(n^2).
    One can further improve upon this by reducing the space complexity to o(1), the following method has time complexity of o(n^2) and space complexity of o(1), which out performs dynamic programming method in terms of space complexity. In this program all possible palindromes of odd and even length are generated and at the end the longest palindrome if exists is returned.

    class Solution {
    public:
        string longestPalindrome(string s) {
      
    int start = 0;
     int maxLength = 1; 
    string res;
       
        if(s.length()==1)
           return s;
        int low, high;
        for (int i = 1; i < s.length(); ++i)
        {
            low = i - 1;
            high = i;
            while (low >= 0 && high < s.length() && s[low] == s[high])
            {
                if (high - low + 1 > maxLength)
                {
                    start = low;
                    maxLength = high - low + 1;
                }
                --low;
                ++high;
            }
             low = i - 1;
            high = i + 1;
            while (low >= 0 && high <s.length() && s[low] == s[high])
            {
                if (high - low + 1 > maxLength)
                {
                    start = low;
                    maxLength = high - low + 1;
                }
                --low;
                ++high;
            }
        }
         res = s.substr(start,maxLength);
    return res;            
    
        
    }
    };
    

  • -19
    W
    class Solution {
    public:
        ListNode *swapPairs(ListNode *head) {
            if(NULL == head || NULL == head->next)
                return head;
            ListNode *p = head;
            ListNode *q = p->next;
            ListNode *k = q->next;
            q->next = p;
            p->next = swapPairs(k);
            return q;
        }
    };

  • 0
    V

    Manacher Algorithm O(n) algorithm, this algorithm achieves linear time complexity by taking the advantage of the certain characteristics or observations about a palindrome and a sub-palindrome

    public class Solution {
        
        public static String longestPalindrome(String s) {
        if (s==null || s.length()==0)
          return "";
     
        char[] s2 = addBoundaries(s.toCharArray());
        int[] p = new int[s2.length]; 
        int c = 0, r = 0; // Here the first element in s2 has been processed.
        int m = 0, n = 0; // The walking indices to compare if two elements are the same
        for (int i = 1; i<s2.length; i++) {
          if (i>r) {
            p[i] = 0; m = i-1; n = i+1;
          } else {
            int i2 = c*2-i;
            if (p[i2]<(r-i)) {
              p[i] = p[i2];
              m = -1; // This signals bypassing the while loop below. 
            } else {
              p[i] = r-i;
              n = r+1; m = i*2-n;
            }
          }
          while (m>=0 && n<s2.length && s2[m]==s2[n]) {
            p[i]++; m--; n++;
          }
          if ((i+p[i])>r) {
            c = i; r = i+p[i];
          }
        }
        int len = 0; c = 0;
        for (int i = 1; i<s2.length; i++) {
          if (len<p[i]) {
            len = p[i]; c = i;
          }
        }
        char[] ss = Arrays.copyOfRange(s2, c-len, c+len+1);
        return String.valueOf(removeBoundaries(ss));
      }
     
      private static char[] addBoundaries(char[] cs) {
        if (cs==null || cs.length==0)
          return "||".toCharArray();
     
        char[] cs2 = new char[cs.length*2+1];
        for (int i = 0; i<(cs2.length-1); i = i+2) {
          cs2[i] = '|';
          cs2[i+1] = cs[i/2];
        }
        cs2[cs2.length-1] = '|';
        return cs2;
      }
     
      private static char[] removeBoundaries(char[] cs) {
        if (cs==null || cs.length<3)
          return "".toCharArray();
     
        char[] cs2 = new char[(cs.length-1)/2];
        for (int i = 0; i<cs2.length; i++) {
          cs2[i] = cs[i*2+1];
        }
        return cs2;
      }    
    }
    

    reference Manacher Algorithm


  • 1
    W

    This is my code using Dynamic Programming which has a running time and space cost of O(n*n).

    public class Solution {
        public String longestPalindrome(String s) {
            int left=0;
           int max=0;
            int len=s.length();
            int right=len-1;
            boolean huiwen[][]=new boolean[len][len];
            for(int i=0;i<len;++i) {
                for(int j=0;j<=i;++j) {
                    if(i -j>=2 ) {
                        if(s.charAt(i)==s.charAt(j)&& huiwen[j+1][i-1]) {
                            huiwen[j][i]=true;
                            
                        }
                        else {
                            huiwen[j][i]=false;
                        }
                    } else {
                        if(i==j) {
                            huiwen[i][i]=true;
                        }
                        else {
                            if(s.charAt(i)==s.charAt(j)) {
                            
                                huiwen[j][i]=true;
                            }
                            else {
                                huiwen[j][i]=false;
                            }
                        }
                    }
                    if(i-j+1>=max && huiwen[j][i]) {
                        max=i-j+1;
                        left=j;
                        right=i;
                    }
                }
            }
            return s.substring(left,right+1);
        }
    } 

  • 0
    R

    why do not you explain ? and just waste our time with seeing your solution>


Log in to reply
 

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