문자열 뒤집기 [리트코드] 5. Longest Palindrome Substring

팰린드롬 문제이다.

문자열 뒤집기는 s = s[::-1]와 같이 할 수 있고
리스트 안에 있는 값들의 경우에는 s.reverse()메서드를 활용하여 뒤집을 수 있다. str은 reverse함수를 사용할 수 없다.

이를 활용하여

class Solution:
    def longestPalindrome(self, s: str) -> str:
        palindromes = []
        for i in range(len(s)):
            for j in range(i,len(s)):
                if s[i:j+1] == s[i:j+1][::-1]:
                    palindromes.append(s[i:j+1])
        palindromes = sorted(palindromes,key=len)
        return palindromes[-1]

문자열 속 팰린드롬을 모두 추출하고, 가장 큰 값을 계산하니 시간초과가 나왔다. 스스로가 생각했을 때도 쉬운거지 효율적인 방법으로 느껴지지는 않았다. 그래서 각 인덱스마다 한쪽은 역방향으로 for 문을 작성해서 각 인덱스마다 가장 큰 팰린드롬을 만나면 다음으로 넘어가도록 하였다.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        palindromes = []
        for i in range(len(s)):
            for j in range(len(s)-1,-1,-1):
                if s[i]==s[j] and s[i:j+1] == s[i:j+1][::-1]:
                    palindromes.append(s[i:j+1])
                    break
                else:
                    continue
        palindromes = sorted(palindromes,key=len)
        return palindromes[-1]

결과적으로 제출은 받았는데

효율적이지는 않은 것 같다,,

파이썬 알고리즘 인터뷰에서는 투 포인터를 활용해서

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

        result = ''
        # 슬라이딩 윈도우 우측으로 이동
        for i in range(len(s) - 1):
            result = max(result,
                         expand(i, i + 1),
                         expand(i, i + 2),
                         key=len)
        return result

위와 같이 길이를 확장해나가며 팰린드롬을 찾고, 찾을 때마다 가장 긴 팰린드롬을 갱신하는 방식이었다. 그리고 이가 훨씬 더 적은 시간과 메모리를 차지했는데, 팰린드롬의 길이가 1일 때나, 자체가 팰린드롬인 경우를 제외하는 처리도 하였고,,

무엇보다 extend함수를 보니 인덱스 값 하나에서 while문을 통하여 점점 앞뒤에 붙는 값을 비교하며, 그 인덱스가 팰린드롬의 중앙의 값인지를 빨리 판별할 수 있었다. expand(i,i+1)는 짝수개수의 팰린드옴에 대비한, expand(i,i+2)는 홀수개수의 팰린드롬에 대비한 코드이다.