[2021][01]Longest Palindrome Substring

문제정보

문제요약

문제에서 원하는 것은 엄청 단순하다, 문자열 s가 주어질 때 s에서 가장 긴 팔린드롬 부분 문자열을 반환하는 문제이다.

제약사항

• 1 <= 문자열 s의 길이 <= 1000
• 문자열 s는 영어 소문자 또는 대문자로 구성

문제접근

1. Brute Force 로 푸는 방법이 있다. 이중 for 문을 돌면서 i번째 문자를 중심으로 하는 가장 긴 부분 문자열을 찾는 방법이다. 이 방법으로 풀면 100% 시간 초과가 발생한다.

2. 다음 방법은 Brute Force에서 반복된 부분에 대해서 다이나믹 프로그래밍을 활용한다. 알고리즘의 이름은 Manacher 알고리즘으로 불린다.

   1. i 번째 인덱스를 중심점으로 하는 가장 긴 팔린드롬의 길이를 A 배열에 저장한다.
   2. j < i를 만족하는 j 중에서 p 번째 인덱스를 중심점으로 하는 가장 긴 팔린드롬의 오른쪽 인덱스를 r이라고 하자. r과 p의 초기값은 0으로 하자.
   3. 문자열 s의 처음부터 끝까지 순회하면서 A의 값을 초기화한다. 다음은 초기화 규칙이다.
      • i <=r 이면 A[i] = min(r-i, A[2*p]-1])
      • i<=r 는 j < i를 만족하는 j 중에서 p를 중심으로 하는 가장 긴 팔린드롬 부분문자열의 오른쪽 끝 인덱스(r) 범위에 속한다는 의미이다.
      • i > r 이면 A[i] = 0
      • i >r은 p를 중심으로 하는 가장 긴 팔린드롬의 부분문자열의 오른쪽 끝보다 더 오른쪽에 있어서 지금까지 계산한 A값을 사용하지 못한다는 의미이다.
   4. A를 초기화한 후에 s[i - A[i] - 1] == s[i + A[i] + 1] 인 동안에 i를 계속해서 증가시킨다.
   5. 모든 문자열을 순회한 후에 A에서 최대값을 갖는 maxIndex를 찾으면, 그 maxIndex를 중심으로 하는 팔린드롬이 찾는 가장 긴 팔린드롬 부부문자열이 된다.

3. 짝수 길이 문자열에 Manacher 알고리즘을 사용하면 가장 긴 팔린드롬 부분문자열을 찾을 수 없다. 그래서 문자열 s가 주어질 때 주어진 문자사이 마다 '#'이나, '@'을 추가한다면 Manacher 알고리즘을 적용해서 정답을 찾을 수 있다.

코드

class Solution:
    def longestPalindrome(self, s: str) -> str:
    
    
        def addSharp(string) -> str:
            result = '#'
            for ss in string:
                result += ss + '#'
            return result
        
        def manacher(string) -> str:
            sharped = addSharp(s)
            a = [0] * len(sharped)
            p = r = 0
            for i in range(len(sharped)):
                if i <= r:
                    a[i] = min(r - i, a[2 * p - i])
                else:
                    a[i] = 0
                    
                while i - a[i] -1 >= 0 and i + a[i] + 1 < len(sharped) and sharped[i - a[i] - 1] == sharped[i + a[i] + 1]:
                    a[i] += 1
                
                if r < i + a[i]:
                     # r은 반지름이 아니라 i 번째 문자를 중심으로 하는 가장 긴 팔린드롬의 가장 길이
                    r = i + a[i]
                    p = i
            maxIndex = a.index(max(a))
            answer = sharped[maxIndex-a[maxIndex]:maxIndex+a[maxIndex] + 1].replace('#', '')
            return answer
        
        return manacher(s)