5. Longest Palindromic Substring 풀이

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

Longest Palindromic Substring - LeetCode

문제 :

가장 긴 palindromic 한 문자열을 리턴하는 것.

풀이 :

첫 번째는 인덱스를 하나하나 늘려가면서 왼쪽과 오른쪽으로 expanding 해 나가는 방법이 있다. 이때 주의해야 할 점은 palindrome의 길이가 홀수인지 짝수인지 알 수 없기 때문에 두 경우를 모두 체크해줘야 한다.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        
        def helper(l, r) :
            
            while l >= 0 and r < len(s) and s[l] == s[r] :
                l -= 1
                r += 1
                    
            return (l+1, r)
        
        dist = lambda x : x[1]-x[0]
        pos = (0, 0)
        
        for i in range(len(s)) :
            
            x = helper(i, i)
            y = helper(i, i+1)
            
            pos = max(pos, x, y, key=dist)
            
        l, r = pos
        return s[l:r]

두 번째로는 Dynamic programming을 사용하여 푸는 방법이 있다. 사실 시간 복잡도는 같으나, 비슷한 부류의 문제의 해결법으로 종종 등장하니 알아두면 좋을 것이다.

```

 Example : s = 'babad'
 
        (0) (1) (2) (3) (4)
    j\i| b | a | b | a | b
    ______________________
(0)  b | 1 | 0 | 1 | 0 | 1
    ______________________
(1)  a | 0 | 1 | 0 | 1 | 0
    ______________________
(2)  b | 0 | 0 | 1 | 0 | 1
    ______________________
(3)  a | 0 | 0 | 0 | 1 | 0
    ______________________
(4)  b | 0 | 0 | 0 | 0 | 1


```

class Solution:
    def longestPalindrome(self, s: str) -> str:
        
        n = len(s)
        dp = [[False]*n for i in range(n)]
        output = ''
        
        for end in range(n) :
            for start in range(end+1) :
                
                if s[start] == s[end] :
                    
                    l = end-start+1
                    # 현재 문자열의 길이가 3보다 작고 가르키는 문자가 같다면 palindrome.
                    # 다른 경우는 현재 start와 end 사이에 있는 문자열이 palindrome 인지를 체크해야함.
                    # ex. a, aa, bb ...
                    dp[start][end] = l<3 or dp[start+1][end-1] 
                    
                    if l > len(output) and dp[start][end] :
                        output = s[start:end+1]
        
        return output