[문자열 조작] 06 가장 긴 팰린드롬 부분 문자열(Longest Palindromic Substring) ✔

<LeetCode 문제>

https://leetcode.com/problems/longest-palindromic-substring/

Longest Palindromic Substring - LeetCode

<풀이>

브루트포스로 모든 substring에 대해 탐색을 하게 되면 코드가 다음과 같습니다. 모든 substring을 탐색하고 안에서는 O(1)이라고 생각하여 코드를 작성했는데 now_s == now_s[::-1]에서 뒤집고 비교하는 과정이 O(N)이므로 전체 시간복잡도가 O(N³)이 되고 N이 최대 1000이므로 시간초과가 납니다.(1억=10⁸)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        longest_p = "" #가장 긴 palindrome 저장할 str
        
        for i in range(len(s)+1):
          for j in range(i,len(s)+1): #모든 연속된 substring탐색
            now_s = s[i:j]
            
            if now_s == now_s[::-1]: #palindrome일때
              if len(longest_p) <= len(now_s): #기존 logest_p보다 길면 갱신
                longest_p = now_s
                
        return longest_p

 

문제를 다이나믹 프로그래밍을 통해 풀 수 있지만, 직관적으로 이해가 어렵습니다. 따라서 투 포린터가 중앙을 중심으로 확장하는 형태로 풀이를 진행하면 다음과 같습니다. 홀수(3칸)과 짝수(2칸)의 투 포인터를 이동시키며 풉니다.

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]:
                left-=1
                right+=1
            return s[left+1:right]
        
        # 해당사항이 없을때 빠르게 리턴
        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

<학습내용>

1. 투 포인터를 이용하는 방식

<학습이 필요한 내용>

1. 최장 공통 부분 문자열(Longest Common Substring) with 다이나믹 프로그래밍
2. 유니코드와 UTF-8 관련 내용

 

https://github.com/HoYoungChun/Algorithm_PS/tree/master/String

GitHub - HoYoungChun/Algorithm_PS: Baekjoon Online Judge, Programmers, LeetCode problem solving by Python, C++