[LeetCode] 5. longest_palindromic_substring (Medium) 2023/4/28

문제 제목	정답률	난이도
5. longest-palindromic-substring	32.4%	Medium

Longest Palindromic Substring - LeetCode

 

문제요약

가장 긴 팰린드롬 부분 문자열을 구하여라
조건 1) 문자열이 입력으로 주어진다
조건 2) 팰린드롬이란 앞에서부터 읽어온 것과 뒤에서부터 읽어온 것이 같은 문자열을 말한다
 

 
Step0. 극단적인 경우 예외처리

문자열의 길이가 0일 경우 -> 해당 문자열 반환
문자열의 길이가 1일 경우 -> 해당 문자열 반환
문자열 자체가 팰린드롬 일 경우 -> 해당 문자열 반환
 
 

Step1. 제일 긴 문자열의 길이를 세는 문제이므로 주어진 문자열의 길이부터 차례대로 계산

 
 

구현 (4406 ms)

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
		
        #Step 0
        if len(s)<2 or s==s[::-1]:
            return s
        #Step 1
        longest_palindrome=""
        nowlen=len(s)
        while(nowlen>=2):
            for left_index in range(0, len(s)-nowlen+1):
                nowstr=s[left_index:left_index+nowlen]
                if(nowstr==nowstr[::-1]):
                    return nowstr
            nowlen-=1

        return s[0]

속도가 느린 이유 : while문장 안에 for 문장 안에 if 문장이 있기 때문.
 
 

지향하는 풀이 - 투 포인터

찾은 팰린드롬을 중심으로 양 옆으로 확장하는 두개의 포인터를 이용

• 짝수 칸의 palindrome 판단
• 홀수 칸의 palindrome 판단

 

Step1. 짝수, 홀수 팰린드롬을 찾는다.

문자열의 길이가 0일 경우 -> 해당 문자열 반환
문자열의 길이가 1일 경우 -> 해당 문자열 반환
문자열 자체가 팰린드롬 일 경우 -> 해당 문자열 반환
 
 

Step2. 해당 팰린드롬을 기준으로 양옆을 확장해 팰린드롬인지 확인 -> 새로운 함수 정의

 

iterable 객체 안에서 key 값을 기준으로 제일 큰 값을 출력하는 함수

max(iterable, key=None)

 

구현(621ms)

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        # step 2
        def increase_index(left:int, right:int):
            while(left>=0 and right<=len(s) and s[left]==s[right-1]):
                left-=1
                right+=1
            return s[left+1: right-1]
    
        # step 0
        if len(s)<2 and s==s[::-1]:
            return s
        longest_palindrome=''
        for left_index in range(0, len(s)-1):
            # step 1 길이가 홀수, 짝수인 포인터 나눠서 판단
            longest_palindrome=max(longest_palindrome, increase_index(left_index, left_index+2),increase_index(left_index, left_index+3), key=len)
        return longest_palindrome

 

 
책에서의 구현(118ms)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def increase_index(left:int, right:int)->str:
        	#step2
            while left>=0 and right<len(s) and s[left]==s[right]:
                left-=1
                right+=1
            return s[left+1:right]
        
        longest_palindrome=''
        #step 0
        if len(s)<2 or s==s[::-1]:
            return s
        #step 1
        for left_index in range(0, len(s)-1):
            longest_palindrome=max(longest_palindrome, increase_index(left_index, left_index+1), increase_index(left_index, left_index+2), key=len)
        return longest_palindrome

두 방법의 차이점은 while 조건절에 s[right-1] s[right]으로 연산과, s[left+1, right-1] s[left+1, right]을 사용했는지  뿐인데 시간이 여섯배정도 차이가 나서 놀랐다.