[오답노트] LeetCode #5 Longest Palindrome Substring

교훈
반복 연산은 한번 한번이 소중하다. 한번 했을 때, 최대한 많은 정보를 구하고 다음으로 넘어가자.
짜기 쉬운 코드도 좋지만, 진짜 사람한테 줬을 때 직관적으로 어떻게 풀지부터 먼저 생각해봐라.

• LeetCode 문제 링크
• 출처 : 박상길 저, 파이썬 알고리즘 인터뷰, p.159

문제

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

문자열 s의 가장 긴 팰린드롬 부분 문자열을 return하라.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

발상

홀수 길이의 팰린드롬과 짝수 길이의 팰린드롬은 함께 계산하기 무척 까다롭다.
그러므로, 홀수 길이와 짝수 길이는 별도로 계산하여야 한다.

Solution #1

가장 긴 팰린드롬이기 때문에, 가장 긴 후보부터 역으로 계산하면 어떨까?

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) < 2 or s == s[::-1]:
            return s
        for i in range(len(s) - 1, 1, -1):
            for j in range(len(s) - i + 1):
                substr = s[j:j+i]
                if substr == substr[::-1]:
                    return substr
        return s[0]

통과하긴 한다. 하지만 Runtime이 6676ms로, 책의 풀이인 402ms보다 훨씬 느리다.
저게 획기적인 발상이라고 생각할 지 모르지만, 엄밀히 따지면 그냥 Brute Force다.

위의 풀이는 O(n^3)이다. for문 2개에 substr == substr[::-1] 연산도 선형 연산이기 때문이다.

Solution #2

for문을 하나만 쓰고 계산할 수는 없을까?

문자열의 각 문자를 한번씩만 도는데, 한번 돌 때 그 문자를 중심으로 해서 만들 수 있는 최대 길이의 팰린드롬을 알아야만 한다!

전진하는 2개의 투 포인터.

• 짝수 길이의 팰린드롬을 찾는다. 길이 2에서 시작하며, 2부터 막히면 길이 0을 반환한다.
  만약 길이 2가 성공한다면, 좌우에서 하나씩 더 늘려 길이 4를 체크해본 뒤, 아니라면 길이 2를 반환한다.
• 홀수 길이의 팰린드롬을 찾는다. 길이 3에서 시작하며, 3부터 막히면 길이 1을 반환한다.
  만약 길이 3이 성공한다면, 좌우에서 하나씩 더 늘려 길이 5를 체크해본 뒤, 아니라면 길이 3을 반환한다.

풀이

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) < 2 or s == s[::-1]:
            return s
        
        def expand(left: int, right: int) -> str:
            while 0 <= left and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return s[left+1 : right] # left+1부터 right-1 까지는 palindrome 확정이기 때문에

        result = ''
        for i in range(len(s) - 1):
            result = max(result, expand(i, i+1), expand(i, i+2), key=len)
        if len(result) == 1:
            return s[0]
        return result