5. Longest Palindromic Substring

5. Longest Palindromic Substring

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

문제)

솔루션1)

middle 문자를 정하고 왼쪽, 오른쪽 포인터를 정해서 비교해서 동일한 문자면 한 칸씩 이동하면서 회문임을 확인한다.

시간 복잡도 : O(n*n)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def get_palindrome(left, right):
            # 왼쪽, 오른쪽으로 이동하면서 회문을 탐색
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1               
            return s[left+1:right]
        
        longest_palindrome = ''
        for i in range(len(s)):
            # 문자열 홀수 케이스          
            palindrome = get_palindrome(i, i)
            if len(longest_palindrome) < len(palindrome):
                longest_palindrome = palindrome
            
            # 문자열 짝수 케이스          
            palindrome = get_palindrome(i, i+1)
            if len(longest_palindrome) < len(palindrome):
                longest_palindrome = palindrome
                
        return longest_palindrome