Using Longest Palindrome


  • 4
    N
        public String shortestPalindrome(String s) {
            if (s == null || s.length() <= 1) return s;
            // find the longest palin beginning at the left
            int l = s.length();
            int maxL = 0;
            for(int i = 0; i <= l /2 ; i++) {
                maxL = Math.max(maxL, Math.max(expand(s, i, false),expand(s, i, true)));
            }
            // use maxL as point
            String suffix = s.substring(maxL+1);
            return new StringBuffer(suffix).reverse().toString() + s.substring(0, maxL+1) + suffix;
        }
        
        // return the end index if the palin starts at beginning
        private int expand(String s, int i, boolean isCenter) {
            int j = isCenter? i: i+1;
            while(i >=0 && j < s.length() && s.charAt(i) == s.charAt(j)){
                i--;
                j++;
            }
            // only return if goes to the start
            if (i < 0 ) return --j;
            return -1;
        }

  • 0
    R

    I see that this code is accepted, then I want to ask judge to increase the limit time for C++, because I have written almost the same idea, but I am struggling for hours with time limit, and cannot pass, or if you could see some differences, I appreciated if you could mention it. Actually I believe that my code should be faster than what he did as I return back the result the moment I find the result, however, he need to traverse the whole l/2 element in the for loop, but still it does not pass the time limit

    class Solution {
    public:
        string shortestPalindrome(string s) {
            int n=s.size(), mid=(n+1)/2;
            string temp;
            for(int i=mid; i>=1; --i){
                if(expand(s, i-1, i, temp)){
    		        return temp;
                }
                if(expand(s, i-1, i-1, temp)){
    		        return temp;
                }
            }
        }
    private:
        bool expand(string& s, int l, int r, string& temp){
            int n=s.size();
            if(n%2==1 && r==(n+1)/2) return false;
            while(l>=0 && r<n && s[l]==s[r]){
                l--;
                r++;
            }
            l++; r--;
            if(l!=0) return false;
            string first_part=s.substr(r+1, n-(r+1));
            reverse(first_part.begin(), first_part.end());
            temp=first_part+s;
            return true;
        }
    };
    

Log in to reply
 

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