LeetCode) 가장 긴 팰린드롬 부분 문자열

 

 

영어를 몰라서 첫문자와 끝문자가 같은 부분을 출력하는 로직을 짰다가 다 지웠다..

팰린드롬 문자란 뒤집어도 같은 문자를 뜻한다.

예시로 'bsb' 를 꺼꾸로 뒤집어도 'bsb'가 되니 팰린드롬 문자에 해당한다.

총 3가지 로직을 소개하겠다.

 

 

처음에는 문자열을 2~n개씩 nlogn번 검사하는 로직이다.

예상되는 시간복잡도는 O(nlogn)

이 로직은 통과 했지만 시간이나 메모리가 다른 로직에 비해 비효율적이였다.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if s == s[::-1]:
            return s

        tl = []
        for i in range(len(s)):
            for j in range(len(s) - 1, i - 1, -1):
                if s[i] == s[j]:
                    if s[i:j + 1][::-1] == s[i:j + 1]:
                        tl.append(s[i:j + 1])

        return max(tl, key=len)

 

 

 

그 다음으로 짜본 로직은 n~2개씩 nlogn번 검사하는 로직이다.

위 로직과는 다르게 답을 찾으면 바로 리턴할 수 있다는 장점이 있는 코드다.

하지만 이 로직은 통과하지 못했다. 

테스트 케이스의 return값이 대부분 작은 값으로 이루어져 있어서 그런것으로 추정된다. 

class Solution:
    def longestPalindrome(self, s: str) -> str:
        cnt = 0
        for i in range(len(s)-1,-1,-1):
            for j in range(len(s)-i):
                cnt +=1
                if s[j:i+j+1] == s[j:i+j+1][::-1]:
                    return s[j:i+j+1]

 

 

 

결국 답안을 보고 문제를 풀게되었는데 확연하게 실행시간이나 메모리 부분이 효율적이였다.

이 방식은 시간복잡도가 O(n)이다. 일단 키워드를 찾은 뒤 확장시켜가며 같은 부분을 늘려가는 코드다.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        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

        cnt = 0
        result = ''
        for i in range(len(s)-1):
            result = max(result, expand(i,i+1), expand(i,i+2),key=len)
            cnt += 1

        return result