[Python/LeetCode] 5. Longest Palindromic Substring

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

 

입력 : 숫자와 알파벳으로 이루어진 문자열 s(소문자만 포함인가?)

출력 : 가장 긴 팰린드롬 부분 문자열

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

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

 

팰린드롬에 관한 개념은 다음 글 참고.

https://cuffyluv.tistory.com/117

[Python/leetcode] 125. Valid Palindrome

 

---

직관 및 접근

이거 알고리즘 시간에 배운 longest common substring처럼 DP로 풀어야 할 것 같은데..

일단 DP 말고 풀이 있나 생각해보자.

 

여기서 책 확인

 

책에 따르면, 이 문제는 앞서 말한 longest common substring, subsequence처럼 DP로 풀 수 있는 대표적인 문제이나,

예상과는 달리 DP로 풀 시 실행 속도가 늦다고 함.

따라서 여기선 직관적이면서 성능이 좋은, 투 포인터 기반 중앙을 중심으로 확장하는 형태로 풀이하면 좋다 함.

---

공부내용

투 포인터는 아래 글 참고.

https://cuffyluv.tistory.com/118

[Python/leetcode] 344. Reverse String

* max() 함수에 동일한 우선순위의 매개변수들이 들어가면?

- 만약 `max(before, now, key = len)` 했는데, before랑 now 가 같은 길이 다른 문자열이면?

=> 같은 우선순위를 가지는 게 있으면 먼저 등장한 인자를 선택한다.

=> 아래 글에 정리해 두었으니 참고하자.

https://cuffyluv.tistory.com/125

[알고리즘] 안정 정렬 vs 불안정 정렬

 

---

풀이

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # 팰린드롬 판별 및 투 포인터 확장
        # s[left] == s[right]: 이 팰린드롬인지 확인하는 조건.
        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), # 2칸짜리 포인터
                         expand(i, i + 2), # 3칸짜리 포인터
                         key=len) # 길이 기준으로
        return result

주석과 책을 잘 읽어보자.

 

2칸짜리 포인터랑 3칸짜리 포인터를 한 인덱스씩 옮겨나가며,

각 포인터가 팰린드롬이면 그걸 확장해나가며 그 인덱스에서의 가장 긴 팰린드롬을 찾는 것.

그렇게 모든 인덱스를 다 돌았을 때 나온 가장 긴 놈이 가장 긴 팰린드롬 부분 문자열이 됨.

제출 결과 `41ms`가 나왔는데, 

다른 분들 런타임을 보니 `1000ms 이하는 대부분 투포인터`, `1000ms 이상은 대부분 DP`를 사용한 풀이었다. 

확실히 책에 나온대로 DP로 풀 수 있는 대표적인 문제긴 하나, (최소한 이 문제에 한해서는) 투 포인터 풀이가 더 성능이 좋은 것을 확인할 수 있다.

# 출처 : 리트코드 샘플 코드
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        ans = [0, 0]

        for i in range(n):
            dp[i][i] = True

        for i in range(n - 1):
            if s[i] == s[i + 1]:
                dp[i][i + 1] = True
                ans = [i, i + 1]

        for diff in range(2, n):
            for i in range(n - diff):
                j = i + diff
                if s[i] == s[j] and dp[i + 1][j - 1]:
                    dp[i][j] = True
                    ans = [i, j]

        i, j = ans
        return s[i : j + 1]

참고삼아 2.96%의 1729ms solution sample code를 확인해보니, 위와 같았다.

---

해당 글은 "파이썬 알고리즘 인터뷰(박상길)"을 공부한 내용과 책의 코드가 포함되어 있습니다.

https://github.com/onlybooks/python-algorithm-interview/tree/master