Python solution(KMP)


  • 9
    S
    class Solution:
    # @param {string} s
    # @return {string}
    def shortestPalindrome(self, s):
        A=s+"*"+s[::-1]
        cont=[0]
        for i in range(1,len(A)):
            index=cont[i-1]
            while(index>0 and A[index]!=A[i]):
                index=cont[index-1]
            cont.append(index+(1 if A[index]==A[i] else 0))
        return s[cont[-1]:][::-1]+s

  • 2
    D

    This is very interesting solution based on KMP. Actually, it is based on the failure function or KMP-table.
    And it's pretty cool that the above solution is accepted by leetcode :).

    However, the Solution is apparently failed in the case "aabba". The call on shortestPalindrome function will return "aabba" while the correct answer should be "abbaabba".

    This is a tricky issue. Leetcode please check.


  • 0
    S

    Thank you so much for checking. I have edited the solution. I see why it is important to add a character in the middle of the string. Thanks again!


  • 0

    Thanks @davidtan1890 for catching that! I have added your test case.


Log in to reply
 

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