[Leetcode] 5. Longest Palindromic Substring

Longest Palindromic Substring - LeetCode

Can you solve this real interview question? Longest Palindromic Substring - Given a string s, return the longest palindromic substring in s.   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.

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

🖥️ 시작하며

1. 팰린드롬 확장 함수 정의:
• calc(left: int, right: int) -> str : 주어진 인덱스 left 와 right 를 중심으로 팰린드롬을 확장해 나갑니다. left 와 right 는 각각 줄어들고 늘어납니다.

2. 팰린드롬 탐색:
• 문자열 s 의 각 문자를 중심으로 팰린드롬을 확장합니다.
• 각 문자 i 에 대해 홀수 길이 팰린드롬과 짝수 길이 팰린드롬을 체크합니다. 둘의 구조가 다르기 때문입니다.
• calc(i, i) : 홀수 길이 팰린드롬 체크합니다.
• calc(i, i + 1) : 짝수 길이 팰린드롬 체크합니다.

⚙️ Python

from typing import List


class Solution:
    def longestPalindrome(self, s: str) -> str:
        # 중앙에서부터 앞뒤로 팰린드롬 체크
        def calc(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) == 0:
            return ""

        longest = ""
        for i in range(len(s)):
            # 홀수 팰린드롬 체크
            odd = calc(i, i)
            if len(odd) > len(longest):
                longest = odd

            # 짝수 팰린드롬 체크
            even = calc(i, i + 1)
            if len(even) > len(longest):
                longest = even

        return longest


# 예제 테스트
sol = Solution()
print(sol.longestPalindrome("babad"))
print(sol.longestPalindrome("cbbd"))

📌 소감