문자열 조작 : 가장 긴 팰린드롬 부분 문자열(리트코드 5번)

▶ 문제 : https://leetcode.com/problems/longest-palindromic-substring/

Longest Palindromic Substring - LeetCode

##### 문제 #####
가장 긴 팰린드롬 부분 문자열을 출력하라.

##### 입력 #####
"babad"

##### 출력 #####
"bab"

 

▶ 접근 방법

팰린드롬이 가능한 경우의 문자열을 찾고 해당 문자열을 확장하는 식의 풀이로 접근하였다.
홀수 일 때와 짝수 일때에 해당하는 투포인터를 만들어 문자열을 살펴본다.
해당 포인터 범위 안에 들어온 문자열이 팰린드롬인 경우 그 자리에 멈추고, 투포인터를 확장한다. 

 

▶ 풀이 코드

ex_string = "babad"

def longest_palindrome(string: str) -> str:
    def expand(left:int, right: int) -> str:
        while left >= 0 and right < len(string) and string[left] == string[right]:
            left -= 1
            right += 1

        return string[left + 1:right]
    
    if len(string) < 2 or string == string[::-1]:
        return string
    
    result = ''
    for i in range(len(string) - 1):
        result = max(result, expand(i, i + 1), expand(i, i + 2), key=len)
    
    return result

print(longest_palindrome(ex_string))

 

▶ 관련 링크

2021.11.17 - [알고리즘] - 이분 탐색(Binary Search)이란?