[LeetCode] 214. Shortest Palindrome

📃 문제 설명

(HARD) https://leetcode.com/problems/shortest-palindrome/

• 주어진 string의 front에만 문자열 추가가 가능할 때, 가장 짧은 팰린드롬 문자열을 출력하는 문제이다.

Example 1:

Input: s = "aacecaaa"
Output: "aaacecaaa"

Example 2:

Input: s = "abcd"
Output: "dcbabcd"

🔎 문제 접근

• 주어진 문자열과, 해당 문자열을 reverse한 문자열에 대해, 두 문자열이 겹쳐지는 문자열이 가장 길 때의 합집합을 출력하면 되겠다는 생각이 들었다. 예를 들어 Example 1의 "aacecaaa"의 경우, 이를 뒤집은 문자열 "aaacecaa"에 대해 다음과 같이 생각하며 정답을 찾아갈 수 있는 것이다.

aaacecaa
aacecaaa -> 완벽히 겹쳐지지 않는다
---
aaacecaa
 aacecaaa -> 완벽히 겹쳐진다
aaacecaaa => 정답

• 겹치는 문자열을 찾는 것에 대해서는 KMP 알고리즘 [1] 이 생각났기에 해당 문제를 KMP 알고리즘을 약간 변형하여 풀게 되었다.

✨ 문제 풀이

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        p = [0] * len(s)
        
        #s에 대한 failure function 만들기
        begin, length = 1, 0
        while begin + length < len(s):
            if s[begin + length] == s[length]:
                length += 1
                p[begin + length - 1] = length
            else:
                if length == 0:
                    begin += 1
                else:
                    begin += (length - p[length - 1])
                    length = p[length - 1]
        
        #reversed list와 KMP 알고리즘 진행
        begin, length = 0, 0
        h = s[::-1]
        begin, length = 0, 0
        while begin + length < len(h):
            if h[begin + length] == s[length]:
                length += 1
            else:
                if length == 0:
                    begin += 1
                else:
                    begin += (length - p[length - 1])
                    length = p[length - 1]
        
        #구한 length는 s에서 겹치지 않는 최초의 위치를 뜻하기도 하므로 
        #reversed list의 뒤에 length부터 시작하는 문자열을 합쳐 출력
        return ''.join(h) + s[length:]      

• KMP 알고리즘은 항상 방법을 까먹게 되는 알고리즘이다. prefix와 suffix가 동일한 최대 길이가 failure funcion 이라는 점을 잊지 말자.
• 다른 사람들의 풀이를 보다 발견한 신박한 풀이를 밑에 첨부한다. 원문자열과 뒤집은 문자열의 LCS 길이만큼을 제외한 나머지 문자열은 절대 팰린드롬을 만족할 수 없기 때문에 양 사이드에 추가해주는 방법이다.

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        n = len(s)
        i = 0
        
        for j in range(n - 1, -1, -1):
            if s[i] == s[j]:
                i += 1
        if i == n:
            return s
        
        return s[i:n][::-1] + self.shortestPalindrome(s[:i]) + s[i:]