Longest Palindromic Substring

나의 논리

아 이것도 일단 못풀었다.
아마 백준에서 C++코드로 작년 쯤 팰린드롬 시리즈를 푼 기억이 있다.

첫번째로 한 고민은
재귀를 이용해서 바이너리 서치를 이용 할 수 있을까? 였다.
0 ... len(s) 길이로 시작하여 left : 0 ... mid , right : mid + 1 ... len(s)을 확인해가며 부분문자열의 길이가 1이 되었을때 길이 1 문자열을 리턴한 후, 호출스택을 올라오면서 mid -1 , mid + 1을 탐색 하는 걸 생각했다..
아차.. 길이가 2인 팰린드롬을 구하지 못하는 논리였다.

그 다음 마지막으로 작년에 푼 코드를 보며 동적계획법을 이용 할 수 있을까? 생각을 했다.
2중 for 문 속에 동적계획법을 해 모든 i ... j 범위를 탐색 하는 것이다. 그러다가 문득 나는 문자열을 리턴해야하는데 팰린드롬이 아닐때는 뭘 리턴해야하지? 라고 생각하다 마음이 급해져서 정답을 보기로 했다. 1시간 조금 안되게 고민 한것 같기도 하고

ps 지금 생각해보면 False를 리턴해서 해도 될 듯?

정답 논리

파이썬 알고리즘 인터뷰라는 책을 보고 있는데
2 포인터라는 스킬을 사용한다.
문제에 나온 조건처럼 팰린드롬이 짝수 ('ㅁㅁ') 일수도 있고 ( 'ㅁㅇㅁ')일수도 있다. 그래서 짝수개를 검사하는 포인터, 홀수개를 검사하는 포인터를 사용한다.

가장 짦은 길이의 팰린드롬을 찾은뒤 그 중심을 기준으로 -1, +1 칸씩 확장해나가는 방식이다.

def longestPalindrome(self, s: str) -> str:
        
        def check(left: int, right: int) -> str:
            
            while left >= 0 and right < len(s) 
            		    and s[left] == s[right]:
                left -= 1
                right += 1
                
            return s[left+1:right]
        
        if len(s) < 2 or s == s[::-1]:
            return s
        
        ret = ""
        for i in range(len(s)):
            ret = max(ret, check(i,i+1),check(i,i+2),key=len)
            
        return ret
```