Longest Palindromic Substring [leet code 5]

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

 

팰린드롬 부분 문자열 문제다.

 

Palindromic 팰린드롬이 뭔지 알아보자.

Wiki 를 살펴보니 회문(回文) 또는 팰린드롬(palindrome)은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열(sequence of characters) 등이다. 보통 낱말 사이에 있는 띄어쓰기나 문장 부호는 무시한다라고 나와있다.

 

그럼 이제 문제를 살펴보자.

 

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.

 

조건을 살펴보면 문자 s 의 길이는 1~1000사이로 주어지고, 문자안에 digits 숫자도 포함되는것을 볼 수 있다.

그럼 "asf11fa" 가있다면 "f11f" 도 팰린드롬이 될 수 있다. 

 

어떻게 접근할 수 있을까?

 

내가 시도한 방식은 다음과 같다.

 

1. s의 길이가 2 미만이면 그대로 반환

2. 각 문자를 확인하면서 해당 문자를 중심으로 하는 홀수 길이 팰린드롬 확인

3. 각 문자를 확인하면서 해당 문자와 다음 문자 사이를 중심으로 하는 짝수 길이 팰린드롬 확인

4. 양쪽으로 확장하면서 팰린드롬 순회

5. 팰린드롬 길이가 이전에 찾은 최대 길이보다 길면 시작 위치와 길이 갱신

6. return

 

순으로 진행된다. 

이 알고리즘의 시간 복잡도는 O(n^2)이라 통과 안될 줄 알았는데 생각보다 빠른 속도로 통과됐다.

 

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) < 2:
            return s
        
        start = 0
        max_len = 1
        
        for i in range(len(s)):
            # 홀수 길이 팰린드롬 확인
            left, right = i, i
            while left >= 0 and right < len(s) and s[left] == s[right]:
                if right - left + 1 > max_len:
                    start = left
                    max_len = right - left + 1
                left -= 1
                right += 1
            
            # 짝수 길이 팰린드롬 확인
            left, right = i, i + 1
            while left >= 0 and right < len(s) and s[left] == s[right]:
                if right - left + 1 > max_len:
                    start = left
                    max_len = right - left + 1
                left -= 1
                right += 1
        
        return s[start:start + max_len]