Python solution(KMP)

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

  • 2

    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

    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.