6. Longest Palindromic Substring

리트코드

중앙을 중심으로 확장하는 풀이

• 다이나믹 프로그래밍으로 풀 수 있는 전형적인 문제다.

• 여기서는 투포인터가 중앙을 중심으로 확장하는 형태로 풀이한다.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        #팰린드롬 판별 및 투 포인터 확장
        
        def expand(left: int, right: int) -> str:
            while left >= 0 and right <=len(s) and s[left] == s[right -1]:
                left -= 1
                right += 1
            return s[left + 1: right - 1]
        
        #해당사항이 없을 때 빠르게 리턴
        
        if len(s) < 2 or s==s[::-1]:
            return s
        
        result =''
        
        #슬라이딩 윈도우 우측으로 이동
        
        for i in range(len(s)-1):
            result = max(result,
                            expand(i, i+1),
                            expand(i, i+2),
                            key=len)
            
        return result
        

• 슬라이싱과 s[3]처럼 인덱스로 직접 조회하는 것은 숫자를 표기하는 방식이 다르므로 주의가 필요하다.

  • 예: s = '12345'일 때 s[1:3]은 23이 나오지만 s[3]은 4가 나온다.

• 슬라이딩 윈도우가 문자열의 처음부터 끝까지 우측으로 이동한다.

  • expend()로 정의한 중첩함수에서 홀수 , 짝수 2개의 투 포인터가 팰린드롬 여부를 판별하면서 슬라이딩 윈도우처럼 계속 우측으로 이동한다.
  • 이렇게 판별한 최댓값이 최종 결과가 된다.

✔ 투 포인터

• 2칸, 3칸으로 구성된 투 포인터가 슬라이딩 윈도우 처럼 계속 앞으로 전진해나간다. 이 때 윈도우에 들어온 문자열이 팰린드롬인 경우 그 자리에 멈추고, 투포인터가 점점 확장하는 식이다.

• 팰린드롬은 bb처럼 짝수 형태로 증가할 수 있고, bab처럼 홀수일 때도 있다.
  따라서 짝수나 홀수 모든 경우에 대해 판별한다.

  • 홀수와 짝수의 2개의 포인터가 계속 우측으로 이동하다 5에서 홀수 투 포인터가 454로 확장되면서 매칭이 되고,
    34543, 2345432, 123454321까지 확장되면서 가장 긴 값으로 저장된다.

유니코드와 UTF-8

이걸 참조하자