문자열 조작 6 - Longest Palindromic Substring

5. Longest Palindromic Substring

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

My Answer 1: Time Limit Exceeded (177 / 177 test cases passed, but took too long.)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def func(s, p):
            if p == p[::-1] and len(self.ans) < len(p):
                self.ans = p
            
            if len(s) == 0:
                return
            
            func(s[1:], p+s[0])
        
        self.ans = ""
        for i in range(len(s)):
            if len(s[i:]) > len(self.ans):
                func(s[i:], "")
        
        return self.ans

문자열을 하나씩 뜯어서 p 에 붙여줌 => substring

p 가 더 긴 palindrome 이면 self.ans update

더 빠르게 하기 위해서 if len(s[i:]) > len(self.ans): 추가
=> 지금 확인할 문자열이 ans 보다 커야 더 긴 palindrome 을 만날 수 있는 거니까

Solution 1: Accepted (Runtime: 248 ms - 94.18% / Memory Usage: 14.1 MB - 94.44%)

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)):
            result = max(result, expand(i, i), expand(i, i+1), key=len)
        
        return result

투 포인터를 사용한 중앙에서 확장하는 방식

홀수: expand(i, i) 한칸씩 / 짝수: expand(i, i+1) 로 두칸씩 범위를 잡고
expand 함수의 while 문에서 palindrome 만큼 left, right 의 범위를 늘려줌

max, min 함수도 key 를 줄 수 있음
ex) max(a, b, key=len) => 길이가 큰 값이 들어감

• s[::-1] => 빠름
• Python 문자열: 유니코드 사용 & 고정 길이 인코딩 방식

Solution 2: Accepted (Runtime: 4340 ms - 29.66% / Memory Usage: 21.9 MB - 17.85%)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        
        n = len(s)
        # Form a bottom-up dp 2d array
        # dp[i][j] will be 'true' if the string from index i to j is a palindrome. 
        dp = [[False] * n  for _ in range(n)]
        
        ans = ''
        # every string with one character is a palindrome
        for i in range(n):
            dp[i][i] = True
            ans = s[i]
            
        maxLen = 1
        for start in range(n-1, -1, -1):
            for end in range(start+1, n):             
                # palindrome condition
                if s[start] == s[end]:
                    # if it's a two char. string or if the remaining string is a palindrome too
                    if end - start == 1 or dp[start+1][end-1]:
                        dp[start][end] = True
                        if maxLen < end - start + 1:
                            maxLen = end - start + 1
                            ans = s[start: end+ 1]
        
        return ans

DP 사용

모든 s 마다 자기 자신 한 글자는 palindrome 이 되니까 dp[i][i] = True 설정

start 는 맨 뒤에서부터 시작하고, end 는 start 의 오른쪽을 쭉 훑어줌

start 값과 end 값이 같고 그 사이의 값들도 palindrome 이면
(=> if end - start == 1 start, end 딱 두글자만 / or dp[start+1][end-1]: 두글자 이상 있을 때)

dp = True & maxLen 기반으로 ans update

이 문제는 DP 보다는 투 포인터가 더 빠르다