Simple Java solution


  • 2
    M

    The main idea is to find the longest palindrome from the first index, cost O(n)

    public String shortestPalindrome(String s) {
        if(s.length() == 0) return "";
        int len = s.length(), left, right,  maxLen = 0;
        for(int i = 0 ; i < len;){
            left = right = i;
            while(right < len - 1 && s.charAt(right) == s.charAt(right + 1))
                right ++;
            
            i = right + 1;
            
            while(left > 0 && right < len - 1 && s.charAt(left - 1) == s.charAt(right + 1)){
                left --;
                right ++;
            }
            
            if(left == 0 && maxLen < right + 1){
                maxLen = right + 1;
            }
        }
        
        String prefix = new StringBuilder(s.substring(maxLen)).reverse().toString();
    
        return prefix + s;
    }

  • 0
    Q

    I think the complexity is not O(n)
    In the for loop, in most cases, variable i would be increased by 1 at a time. However, the second while loop, might already take O(n) to extend the palindrome centered at left and right. So in the worst case, this algorithm would be O(n^2) or precisely O(1/2 * n^2).
    Or am I wrong?


  • 0
    G
    This post is deleted!

  • 0
    J

    Seems like O(n^2) to me as well because take aacecaaa for example, when i is at index e, the runtime for e itself is already O(n), then you loop through all the character which makes it O(n^2).


  • 0
    P

    @QiZhang1
    I think it is better than o(n^2), I tried to use the same idea by finding longest palindrome from index 0, but ending with ELT, but this solution only takes 8ms.. man, so fast...


  • -1
    Z

    excellent, it's so fast. it's o(n/2), not o(n^2). try case like "aaa...aaa" or "abcd...zabcd...z".


  • -1
    Z

    @QiZhang1 try case like "aaaa....aaa" and "abcd...zabcd...z", in fact, it's o(n/2), not o(n^2)


Log in to reply
 

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