My 9-lines three pointers Java solution with explanation


  • 55

    Explanation

    The key point is to find the longest palindrome starting from the first character, and then reverse the remaining part as the prefix to s. Any advice will be welcome!

    public String shortestPalindrome(String s) {
        int i = 0, end = s.length() - 1, j = end; char chs[] = s.toCharArray();
        while(i < j) {
             if (chs[i] == chs[j]) {
                 i++; j--;
             } else { 
                 i = 0; end--; j = end;
             }
        }
        return new StringBuilder(s.substring(end+1)).reverse().toString() + s;
    }

  • 0
    M

    what is the difference between charAt() and char array indexing?
    Because I failed the test case when I use charAt() and AC by using array indexing.

    Thanks.


  • 0
    X
    This post is deleted!

  • 0
    W

    I also encounter this issue. From my point, using charAt() should be same as array indexing in time complexity when input is large enough, but my solution using the function call results in TLE whereas the other one is accepted.


  • 1
    W

    Dude, your code is time limit exceeded.


  • 1
    X

    The complexity is O(n^2) for aaaaabcaaaaa


  • 0
    M

    it can be further optimized:

    we can update the position of 'end' when traversing between 'chs i' and 'chs j' -- in the block if (chs[i] == chs[j]) {}, update 'end' to be j if chs[j] == s.charAt(0)

    Since in the else block we always decrease end by 1, we have to update 'end' to be j+1 if i is not 0 in the block above


  • 0
    P
    This post is deleted!

  • -1
    I

    Too slow, don't you think?


  • 0
    C

    I had similar idea and wrote c++, but it got TLE for large input

    class Solution {
    public:
        string shortestPalindrome(string s) {
            int i=0, end=s.length()-1, j=end;
            
            while(i<j)
            {
                if (s[i]==s[j])
                {
                    i++;
                    j--;
                }
                else
                {
                    i=0; 
                    end--;
                    j=end;
                }
            }
            
            string t=s.substr(end+1);
            reverse(t.begin(),t.end());
            return t+s;
        }
    };

  • 0
    H

    It seems that the test case has been updated, and now your solution cannot pass all of them because of TLE.


  • 0
    L

    @maxxx char array is very fast since all the characters are placed into fixed size array. CharAt() would be a bit slower.


  • 0
    N
    This post is deleted!

  • 0
    N

    C++ cannot pass with this solution TLE


  • 0
    S

    @coder2
    It 's an O(N^2) algorithm, but the following got AC wich 800+ms.

    int expand_from_center(string &s, int i, int j){
        while(i >= 0 && j < s.length() && s[i] == s[j]) {
            i--;
            j++;
        }
        return i == -1 ? j - i - 1 : -1;
    }
    
    string shortestPalindrome(string s) {
        int len = 0;
        for (int i = s.length() / 2; i >= 0; i--) {
            int p1 = expand_from_center(s, i, i);
            int p2 = expand_from_center(s, i, i+1);
            if (p1 > 0 || p2 > 0) {
                len = max(p1, p2);
                break;
            }
        }
        string pre(s.substr(len));
        reverse(pre.begin(), pre.end());
        return pre + s;
    }

  • 0
    J

    Is complexity is O(N*N)


  • 0
    T

    @ChengZhang said in My 9-lines three pointers Java solution with explanation:

    to find the longest palindrome starting from the first character

    Your idea is right. But this is a brute-force solution to find the longest palindrome starting from the first character.


  • 0
    Y
    This post is deleted!

Log in to reply
 

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