leetcode 5. Longest Palindromic Substring 풀이

문제 :  주어진 문자열에서 가장 긴 대칭하는 substring을 반환하라

Follow up : -

 

아이디어 : 주어진 문자열을 길이가 1 <= s.length <= 1000 로 매우 짧으므로 완전 탐색을 하도록 한다. 이때 max_sub 보다 짧은 구간에 대해서는 탐색하지 않음으로 시간을 단축한다.

 

코드 :

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) == 1:
            return(s)
        
        max_sub = ""
        for idx1 in range(len(s)):
            if (len(s)-idx1) < len(max_sub):
                break
            for idx2 in range(idx1+1,len(s)):
                sub_str = s[idx1:idx2+1]
                if sub_str == sub_str[::-1]:
                    if len(max_sub) < len(sub_str):
                        max_sub = sub_str
        if max_sub == "":
            return (s[0])
        return max_sub

 

학습 포인트 : 처음에는 sliding window와 비슷한 문제로 착각해서 시간을 허비했다. 문제를 잘 이해하고 천천히 풀면 좋을것이다.

 

출처 : leetcode.com/problems/longest-palindromic-substring/