[Leetcode 아주 상세한 문제풀이] 5. Longest Palindromic Substring - 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 5번 문제 Longest Palindromic Substring 다.

우선 문제는 다음과 같다.

 

리트코드 5번 문제 Longest Palindromic Substring 링크

Palindromic Substrings - LeetCode

Palindromic Substrings - LeetCode

 

Given a string s, return the longest palindromic substring in s.

 

Example 1:
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:
Input: s = "cbbd"
Output: "bb"

 

 

문제 설명

우선 Palindrome이란 단어는 우리나라말로 '회문'이란 뜻으로 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 혹은 문자열이다. 대표적으로 이상한 변호사 '우영우', 앞으로 읽어도 거꾸로 읽어도 '우영우'가 회문 문자열이다. 문제는 문자열 s가 주어졌을 때 문자열 안에 존재하는 substring 중 가장 긴 palindrome을 찾아내라는 것이다. 문제 예시 1번에서 보는 것처럼 주어진 문자열이 "babad"일 때 "bab"가 앞으로 읽어도 뒤로 읽어도 똑같은 '가장 긴' palindrome이 되므로 "bab"를 출력하면 된다. 단, 이 경우 "aba"도 "bab"와 길이가 같은 palindrome이 되기 때문에 정답이 된다. 이제 문제를 풀어보자.

 

 

문제 접근법

이제 문제를 풀어보자.

단순히 생각나는 정답은 모든 substring을 체크하는 것이다. 하지만 딱 생각해봐도 문자열 길이가 길어질수록 탐색해야 하는 substring수가 엄청나게 늘어나기 때문에 효율적인 답이 아니다.

회문 구조의 특징을 생각해보면 대칭구조를 이루고 있다는 점이다. 따라서 특정 문자열에서 시작하며 두개의 포인터를 사용하여 앞/뒤 방향으로 검색하다보면 회문 구조를 이루는 substring을 찾을 수 있다.

예를 들어 'abcdefed'라는 문자열이 있을 때 'f' 문자열을 기준으로 양 옆으로 검색하다보면 양쪽 방향에서 같은 거리에 'd'가 위치함을 찾을 수 있고 따라서 'defed'라는 회문 substring을 찾을 수 있다.

 

 

문제 풀이

우선 longest_palindromic_substring이라는 문자열 s를 받는 함수를 정의해준다. (line 1)

그리고 만약 문자열의 길이가 2보다 작다면 그 문자열을 바로 return해준다 (line 2)

회문 구조를 이룰 수 없기 때문이다 (e.g., ab)

그리고 해당 인덱스를 기준으로 양쪽 방향으로 탐색하는 포인터 (left, right)를 설정해준다 (line 8)

이때 left 포인터는 0보다는 같거나 커야 하고 right 포인터는 문자열 길이보다 짧아야 한다 (탐색범위를 벗어난다)

그리고 left, right 포인터가 가리키는 문자열이 같을 경우 포인터를 양쪽으로 한 칸씩 더 옮긴다 (line 10-11)

Line 9 조건에 해당하지 않을 경우 left, right 포인터를 한 칸씩 안쪽으로 이동해준다 (line 12)

탐색을 위해 이미 한 칸씩 더 이동한 상태이기 때문이다.

그리고 문자열 첫번째 인덱스부터 포인터로 탐색을 해보는데 (line 14)

이때 문자열의 길이가 홀수 (odd)인지 짝수 (even)인지 구분하는게 중요하다.

홀수 같은 경우 위에서 설명한 대로 해당 인덱스에서 양쪽 방향으로 동일한 거리를 탐색하면 되지만

짝수 같은 경우 우선 해당 인덱스와 그 다음 인덱스에 해당하는 문자가 같은지 먼저 확인해야 하기 때문이다.

따라서 문자열의 길이가 홀수인 경우 expand_around_center 함수로 포인터를 이동시켜 (line 15)

left 포인터를 시작지점, 그리고 최대 문자열 길이 (max_length)를 구한다. (line 16-18)

반대로 문자열의 길이가 짝수인 경우 인덱스 i와 바로 그 다음 인덱스 i+1부터 탐색을 시작한다 (line 20)

이때 위와 마찬가지로 left 포인터가 위치한 곳이 시작점, 그리고 최대 문자열 길이 (max_length)를 구한다. (line 21-23)

최종적으로 회문 구조인 substring을 출력해야 하기 때문에

시작 지점에 있는 포인터 (start) 그리고 마지막 지점에 있는 포인터 (start+max_length) 그 사이에 있는 문자열을 출력한다.

 

 

문제 풀이 코드

def longest_palindromic_substring(s):
    if len(s) < 2:
        return s
    
    start = 0
    max_length = 1
    
    def expand_around_center(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1
    
    for i in range(len(s) - 1):
        left1, right1 = expand_around_center(i, i)      # odd length palindrome
        if right1 - left1 + 1 > max_length:
            start = left1
            max_length = right1 - left1 + 1
        
        left2, right2 = expand_around_center(i, i + 1)  # even length palindrome
        if right2 - left2 + 1 > max_length:
            start = left2
            max_length = right2 - left2 + 1
    
    return s[start:start + max_length]
 
# Example usage
input_string = "abcabcbb"
result = longest_palindromic_substring(input_string)
print("Longest palindromic substring:", result)
 

 

 

관련 문제

리트코드 3번 Longest substring without repeating characters 문제풀이

리트코드 20번 Valid parenthesis 문제풀이

리트코드 49번 Group anagram 문제풀이

리트코드 76번 Minimum window substring 문제풀이

리트코드 125번 Valid palindrome 문제풀이

리트코드 242번 Valid anagram 문제풀이

리트코드 424번 Longest repeating character replacement문제풀이

리트코드 647번 Palindromic substrings문제풀이

 

5. Longest Palindromic Substring