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

파이썬으로 배우는 알고리즘 책을 공부하며 풀었던 LeetCode문제들을 재정리해보자.

 

# 문제 설명 

5번 Longest Palindrome Substring은 가장 긴 팰린드롬 부분 문자열을 출력하는 문제이다.

 

* 펠린드롬 : 앞뒤가 똑같은 단어나 문장 

Example

 

# 풀이방법 1 - 단순 이중 for문으로 

class Solution:
    def longestPalindrome(self, s: str) -> str:
        
        palindroms = ""
        
        # 문자열의 첫글자와 끝 글자가 같은 문자열 구함 
        for startIdx, c in enumerate(s):
            sameCharIdxGroup = [i for i, ele in enumerate(s) if ele == c and i> startIdx]
 
            for endIdx in sameCharIdxGroup :
                splited_s = s[startIdx:endIdx+1]  
                
                # 문자열이 팰린드롬인지 가장 긴 팰린드롬인지 확인함
                if splited_s == splited_s[::-1] and len(splited_s) > len(palindroms) :
                    palindroms = splited_s    
                                          
        if palindroms == "":
            return s[0]
        else : 
            return palindroms

아이디어 : 이중 for문으로 문자열의 앞과 뒤를 가리키다 값이 같으면, 그 인덱스 사이의 문자열을 split 함.

- palindroms 배열 : 가장 긴 펠린드롬을 저장

- sameCharIdxGroup 변수 : 문자열의 첫 글자와 끝 글자가 같은  문자열 저장 변수로, 이중 for문으로 문자열의 앞, 뒤를 접근하는 방식 사용 (조건, 현재 두번째 for문은 첫번째 for문에서 가리키고 있는 값의 인덱스보다는 커야하며, 가리키는 그 값이 같으면 저장함) 

- splited_s  변수 : 시작 문자와 끝 문자가 같은 문자열로, 팰린드롬인지 확인 절차 거침 

 

 

 

# 풀이 방법 2 - 투 포인터 (슬라이딩 윈도우) (책 풀이 참고)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        
        # 펠린드롬 판별 (이중 포인터-슬라이딩 윈도우)
        # 원리 : 중심 좌표로 부터 양쪽으로 인덱스를 늘려가며 펠린드롬인지 확인 
        def isPalindrome(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
        
        # main문 
        result =''
        for i in range(len(s)-1):
            result = max(result, isPalindrome(i, i+1), isPalindrome(i, i+2), key=len)
        
        return result

원리 : 이중 포인터를 이용한 슬라이딩 윈도우 기법으로 펠린드롬 여부를 판단함 (isPalindrome 함수로 판별, 중심 좌표는 main문)

* 슬라이딩 윈도우 : 중심 좌표를 두고 좌우 양쪽으로 범위를 늘려가는 기법

 

 

| 핵심 |

def isPalindrome(left : int, right : int) -> str : # 펠린드롬 판별 함수

 

# 펠린드롬 중심 좌표 설정 for문 (짝수/홀수 길이 구분)

for i in range(len(s)-1):
            result = max(result, isPalindrome(i, i+1), isPalindrome(i, i+2), key=len)

 

 

# (재풀이) 풀이 방법 2 이용

2022.02.21 재풀이

class Solution:
    def longestPalindrome(self, s: str) -> str:
        
        result = ''
        
        def sliding(left, right) :
            while left >=0 and right < len(s) and s[left] == s[right] :
                left -= 1
                right += 1
            # print(left, right)
            return s[left+1:right] # +1 하는 것 잊지 말기
        
        if len(s) < 2:
            return s
        
        for i in range(len(s)-1) :
            even_len = sliding(i,i+1)
            odd_len = sliding(i, i+2)
            print('i :', i, 'even_len : ' ,even_len, 'odd_len :', odd_len)
            result = max(result, even_len, odd_len, key=len)
            
        return result

 

| 핵심 |  

- [ 슬라이딩 윈도우 : 펠린드롬 문자열 판별 ]

sliding 함수, 인자를 left와 right 인덱스를 받고 left,right  기준으로 양쪽으로 문자열을 확장하는데

이때, 펠린드롬 조건을 만족할때까지만 문자열을 확장하고 값을 return 함 

- [ sliding 함수 호출 : for문 ]

여기서 주목할 점은 펠린드롬 문자열의 길이가 홀수, 짝수 길이일 수도 있으므로,

sliding 함수 호출 시 i+1, i+2로 하여 각각 홀수, 짝수 길이의 문자열도 고려하며 호출한다.

또한, 길이 비교 시 max함수와 key=len을 이용하여 손 쉽게 가장 긴 문자열을 찾아낼 수있다.  

 

 

# 결과 

1차 작성 시

2차 작성 시_재풀이 2022.02.21