(Leetcode) Longest Palindromic Substring

Related:
Longest Palindromic Subsequence:
https://changhaz.wordpress.com/2014/05/25/clrs-longest-palindrome-subsequence/

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

O(n^2) time and O(n^2) space solution:
Maintain a 2d array A, with each member A[i][j] (i always no larger than j) represent whether S’s substring from index i to j is palindrome.

This solution is O(n^2) complexity. It closely passed the bar when we use int array and memset to initialize it. If we initialize it will two level of loop, we will fail with ‘time limit exceeded’.

Instead of 2d array, if we use vector, we will fail with ‘memory limit exceeded’.

Therefore, this algorithm is not efficient

string longestPalindrome(string s) {
         int outstart, outend;
         int maxlen = 0;
        
         int len = s.size();
         
         int vi[len][len];
         memset(vi, 0, len*len*sizeof(int));  
         
         /*
         vector<vector<int> > vi;
         
         for (int i=0;i<len;i++) {
             vector<int> temp(len,0);
             vi.push_back(temp);
         }
         */
         
         for (int i=len-1;i>=0;i--) {
             for (int j=len-1;j>=i;j--) {
                 if (i==j) {
                     vi[i][j] = 1;
                 } else if (i==j-1) {
                     if (s[i] == s[j]) {
                         vi[i][j] = 1;
                     }
                 } else {
                     if (s[i] == s[j] && vi[i+1][j-1]) {
                         vi[i][j] = 1;
                     }
                 }
                 if (vi[i][j] && j-i+1 > maxlen) {
                     maxlen = j-i+1;
                     outstart = i;
                     outend = j;
                 }
             }
         }
         string out = s.substr(outstart, outend-outstart+1);
         return out;
    }

O(n^2) time O(1) space solution:
Consider each possible center of palindromic substring and calculate its length.

string longestPalindrome(string s) {
        if (s.size()==0) return "";
        int maxlen = 0;
        int maxd = 0;
        int maxl = 0;
        int maxr = 0;
        
        for (int i=0;i<s.size();i++) {
            int tempd = getsize(s,i,i);
            int templen = 1+2*tempd;
            if (templen>maxlen) {
                maxlen = templen;
                maxl = i;
                maxr = i;
                maxd = tempd;
            }
            
            tempd = getsize(s,i,i+1);
            if (i+1>=s.size() || s[i] != s[i+1]) continue;
            templen = 2+2*tempd;
            if (templen>maxlen) {
                maxlen = templen;
                maxl = i;
                maxr = i+1;
                maxd = tempd;
            }
        }
        
        string out(s.begin()+maxl-maxd, s.begin()+maxr+maxd+1);
        return out;
        
    }
    
    int getsize(string &s, int l, int r) {
        if (l<0 || r>=s.size() || s[l] != s[r])
            return 0;
        int d = 0;
        while (l>=0 && r<s.size() && s[l-1] == s[r+1]) {
            l--;
            r++;
            d++;
        }
        return d;
    }

O(n) solution:
General idea is, traverse the string, for each index calculate the size of the palindrome substring centered at this character if necessary (main operation). If the current character at index i falls into the range of the palindrome substring centered before i (assume index of the center is c), then we know that this character has its symmetric number indexed i'=2c-i. Here for i we do not need to start from scratch. We could use part of pre-calculated result to be efficient. For this solution, no index falls into the main operation twice, total runtime is O(n).

Here ‘#’ is used to help dealing with both odd and even sized palindrome substring.
‘^’ and ‘$’ is used to avoid complex boarding conditions.

Details is explained here:
http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

My code:

string longestPalindrome(string s) {
        string t = "^";
        for (int i=0;i<s.size();i++) {
            t = t+'#'+s[i];
        }
        t = t+"#$";
        
        int len = t.size();
        vector<int> p(len,0);
        int c=0;
        int r=0;
        
        for (int i=1;i<len-1;i++) {
            if (i<r) {
                int ii = 2*c-i; 
                p[i] = min(p[ii],r-i);
            }
            
            while (t[i+p[i]+1] == t[i-p[i]-1]) {
                p[i]++;
            }
        }
        
        int maxv = 0;
        int maxi = 0;
        for (int i=1;i<len-1;i++) {
            if (p[i] > maxv) {
                maxv = p[i];
                maxi = i;
            }
        }
        
        string temp(t.begin()+maxi-maxv,t.begin()+maxi+maxv+1);
        string out;
        for (int i=0;i<temp.size();i++) {
            if (temp[i] != '#')
                out += temp[i];
        }
        
        return out;
    }
Advertisements
This entry was posted in fail2solve, hardd, leetcode, need2improve, needBetterSol'n and tagged , , . Bookmark the permalink.

One Response to (Leetcode) Longest Palindromic Substring

  1. Pingback: (CLRS) Longest Palindrome Subsequence | Changhaz's Codeplay

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s