[python] LeetCode 5번: Longest Palindromic Substring(Medium)

28 Nov 2020 in Algorithm on LeetCode

---

Problem

Given a string s, return the longest palindromic substring in s.

1 <= s.length <= 1000
s consist of only digits and English letters (lower-case and/or upper-case)

문자열 s가 주어졌을 때, s의 부분문자열중 가장 긴 palindrome을 반환하라.

문제 링크 : 리트코드 5번

---

<Try>

우선 palindrome을 번역하면 “회문”이란 뜻으로 역순으로 읽어도 같은 말이나 구절 혹은 숫자를 말한다. 따라서 “a”, “aba”, “cc”, “ababa” 모두 역순으로 읽어도 본래 구절과 같으므로 palindrome이라 할 수 있다.

이 palindrome의 특징을 이용하면 DP 문제로 해결할 수 있다. 어떠한 문자열 s가 palindrome일 때, 만약 그 문자열의 앞뒤에 같은 문자가 붙여진다면 그 문자열 또한 palindrome이 된다.

Ex) “abba” -> “habbah”

단, 원래 문자열의 길이가 1일 때, 같은 문자가 연속으로 와도 palindrome이 된다는 것을 잊으면 안된다.

Ex) “a” -> “aa”

따라서, 아래 나올 Solution에서는 palindrome의 시작을 1개일 때, 2개일 때로 나누어 확장시켜나갈 것이다.

---

<Solution>

class Solution:  
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        maxLen = 0
        ans = ""
        for i in range(n):
            # 길이가 홀수인 palindrome 조사
            left, right = i, i
            while True:
                if (left >= 0 and right < n) and s[left] == s[right]:
                    if maxLen < right - left + 1:
                        maxLen = right - left + 1
                        ans = s[left:right+1]
                    left -= 1
                    right += 1
                else:
                    break
            
            # 길이가 짝수인 palindrome 조사
            left, right = i, i+1
            while True:
                if (left >= 0 and right < n) and s[left] == s[right]:
                    if maxLen < right - left + 1:
                        maxLen = right - left + 1
                        ans = s[left:right+1]
                    left -= 1
                    right += 1
                else:
                    break
        
        return ans
                

먼저 palindrome 후보의 센터를 문자열 s 전체를 순회하면서 한번씩 정해진다.

정해진 센터를 기준으로 palindrome이 홀수일 때, 짝수일 때로 나누어 양옆으로 한칸씩 확장해가며 더 긴 palindrome이 되는지 확인한다.

while문 부분은 홀수일 때, 짝수일 때 상관없이 같으므로 함수로 묶어 통일시켜도 무방하다.

시간복잡도는 센터를 정하는 데 O(n), 센터를 중심으로 검사하는데 O(n)이 소요되므로 O(n²)이다.