Участник:Lenaermakova/Shortest Palindrome

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/shortest-palindrome/

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        doubled_s = s + "#" + s[::-1]
        current_lens = [0] * len(doubled_s)
        palindrome, i = 0, 1
        while (i < len(doubled_s)):
            if(doubled_s[i] == doubled_s[palindrome]):
                palindrome += 1
                current_lens[i] = palindrome
                i += 1 
            else:
                if (palindrome != 0):
                    palindrome = current_lens[palindrome-1]
                else:
                    current_lens[i] = 0
                    i += 1
        return(s[current_lens[-1]:][::-1]+s)