214. Shortest Palindrome

[zeikar]

Problem link

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

Problem Summary

주어진 문자열이 팰린드롬이 되도록 문자열을 앞에 붙이는 문제.

Solution

처음에는 단순 while 루프를 돌았지만 예외가 발생함. 결국 KMP로 해결

KMP는 현재 인덱스에서 suffix와 같은 prefix의 최대 길이를 구해놓는데, 이를 이용하면 팰린드롬을 구할 수 있다. 주어진 문자열에 뒤집은 문자열을 붙였을 때 prefix와 suffix가 같다는 것은 팰린드롬이라는 것이기 때문이다.
단, 이어 붙일 때 완전히 분리하기 위해서 # 같은 입력에 없는 문자를 넣어주면 된다.

이렇게 하면 KMP의 결과가 가장 긴 팰린드롬 prefix이 되고 이만큼을 제외한 문자열을 앞에 붙이면 전체 문자열이 팰린드롬이 된다.

Source Code

class Solution:
    def shortestPalindrome(self, s: str) -> str:

        def kmp(s):
            i, j = 1, 0
            n = [0] * len(s)
            while i < len(s):
                if s[i] == s[j]:
                    n[i] = j + 1
                    i += 1
                    j += 1
                elif j > 0:
                    j = n[j - 1]
                else:
                    n[i] = 0
                    i += 1
            return n

        next_arr = kmp(s + "#" + s[::-1])
        return s[next_arr[-1]:][::-1] + s