[python]5. Longest Palindromic Substring

Longest Palindromic Substring - LeetCode

 

Longest Palindromic Substring - LeetCode

 

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

입력된 문자열에서 가장 긴 팰린드롬을 찾아 반환하는 문제

1. 팰린드롬을 찾고 

2. 가장 긴 팰린드롬인지 확인 

 

틀린 풀이

class Solution:
    def longestPalindrome(self, s: str) -> str:
  		# 팰린드롬을 담을 리스트   
        palindrome = []
        # 가장 긴 팬린드롬을 담을 변수 
        # max(palindrome, key=len) 으로 찾으면 된다 (아래 같은 방법 사용 x)
        max = ""
        # s 로 만들 수 있는 모든 문자열을 체크하는 코드 
        for i in range(0, len(s)+ 1):
            for j in range(i):
                check_str= s[j:i]
                # 펠린드롬 체크
                # python 은 인덱싱 연산이 빠르기에 [::-1] 으로 팰린드롬 판단 
                temp_str = check_str[::-1]
                # 팰린드롬이면 
                if check_str == temp_str:
                	# 팰린드롬을 담는 리스트에 추가 
                    palindrome.append(check_str)
                    # 길이 비교해서 가장 긴 변수 저장 
                    # max(palindrome, key=len) 사용하면 된다 
                    if len(check_str) > len(max):
                        max = check_str

        return max

# >>> Time Limit Exceeded

"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabc\
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

# 다음과 같은 긴 문자열이 주어졌을 때 타임 에러가 났다

 

올바른 풀이

 

투 포인터가 중앙을 중심으로 확장하는 형태로 코드 작성 (속도 개선)

슬라이딩 윈도우가 오른쪽으로 이동하며 

팰린드롬 일 때 윈도우가 좌, 우로 확장되는 방식 

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # 팰린드롬 판별, 투포인터 이동
        def expand(left: int, right: int) -> str:
        	# s[left] == s[right] 펠린드롬인지 확인 
            while left >= 0 and right < len(s) and s[left] == s[right]:
            	# 펠린드롬이면 윈도우의 크기를 좌, 우로 확장한다 
                left -= 1
                right += 1
            return s[left+1:right]

        # 해당 사항이 없을 때 리턴
        # 0,1개의 문자로 이루어진 문자열이거나 
        # 이미 팰린드롭인 문자열일 땐 expand() 사용하지 않고 바로 통과 
        if len(s) < 2 or s == s[::-1]:
            return s
            
        result = ''
        # 슬라이딩 윈도우 이동
        for i in range(len(s) -1):
        	# expand(i, i+1) 팰린드롬이 짝수일 경우
            # expand(i, i+2) 팰린드롬이 홀수일 경우 
            result = max(result, expand(i, i+1), expand(i, i + 2), key=len)

		# 가장 긴 값 반환 
        return result