[리트코드][Medium] Longest Palindromic Substring

문제

리트코드 Longest Palindromic Substring

가장 긴 대칭(앞에서 보나 뒤에서 보나 같은 글자) 단어 찾기

자료구조 및 알고리즘

• sliding window

문제 풀이 및 회고

Brute-force

메모리는 가장 적게 쓰나, 시간복잡도가 매우 큼

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        n = len(s)
        if n <= 1:
            return s
        
        def check_palindrome(s, start, end):
            word = s[start:end+1]
            if word == word[::-1]:
                return True
            return False
            #for i in range((end-start+1)//2):
            #    if s[start+i] != s[end-i]:
            #        return False
            #return True


        section = [0, 1] # idx 0 만 추가
        for i in range(n-1):
            for j in range(i+1, n):
                if j+1 - i > section[1] - section[0] and check_palindrome(s, i, j):
                    section = [i, j+1]
        return s[section[0]:section[1]] 

Optimized Center Expansion

class Solution(object):
    def longestPalindrome(self, s):
        ans = ''
        c = 0
        if len(s) == 1:
            return s[0]
        for r in range(len(s) - 1):
            k1 = 0
            k2 = 0
            if s[r] != s[r + 1]: # 홀수인 경우
                k1 = r - 1 # set left boundary
                k2 = r + 1 # set right boundary
            else: # 짝수인 경우
                t = r
                k2 = 0
                while t < len(s) and s[t] == s[r]:
                    k2 = t # expand right boundary
                    t += 1
                k1 = r - 1
                k2 += 1
            
            while k1 > -1 and k2 < len(s) and s[k1] == s[k2]:
                    k1 -= 1 # 왼쪽으로 확장
                    k2 += 1 # 오른쪽으로 확장
            if k2 - k1 > c:
                ans = s[k1 + 1:k2] # 정답 갱신
                c = k2 - k1
        return (ans)

Optimized Expansion Using Center Approach

class Solution(object):
    def longestPalindrome(self, s):

        if s == s[::-1]: return s # 만약 전체가 palindrome 인 경우

        c = len(s)-1
        cenLeft, cenRght = 0, 0 # 초기 중심 포인트
        pal = s[0] # Initialize with the first character as the palindrome

        while cenRght < c:
            while cenRght < c:
                if s[cenRght] != s[cenRght + 1]: break  # 짝수 대칭단어에서 오른쪽 경계
                cenRght = cenRght + 1
            i, j = cenLeft, cenRght # 확장 경계

            while i > 0 and j < c:
                if s[i - 1] != s[j + 1]: break # 늘리기
                i -= 1; j += 1

            if len(pal) < j + 1 - i:
                pal = s[i:j+1] # 정답 갱신

            cenRght = cenRght +1 # 다음거로 한칸 이동
            cenLeft = cenRght # 다음거로 한칸 이동
        
        return pal