Longest Palindromic Substrings
가장 긴 팰린드롬 부분 문자열 찾기
문제 이해
5. Longest Palindromic Substring - 문제 링크
문제 설명은 한 줄로, 매우 간단하다.
문자열
s가 주어지고, 이 문자열에서 가장 긴 팰린드롬 부분 문자열을 찾아서 반환하라.
팰린드롬이 무엇인지는 Valid Palindrome 문제에서 설명했으니 참고하자.
간단하게 말하면 앞으로 읽으나 뒤로 읽으나 똑같은 문장을 팰린드롬이라고 한다.
문제 풀이
모든 부분 문자열 확인
문자열이 주어지면 그 문자열의 모든 부분 문자열을 찾아서 팰린드롬인지 확인하는 방법을 생각해 볼 수 있다. 하지만, 문자열의 길이가 최대 1000이고, 팰린드롬인지 판단하는 시간도 고려해야하기 때문에 이 방법은 시간 복잡도가 너무 커진다.
따라서 더 효율적인 방법을 생각해야 한다.
투 포인터
종이에 끄적이면서 고민하다가 생각난 방법인데, 투 포인터 기법이 맞는지는 모르겠다. 어쨌든 두 개의 포인터를 이용하긴 한다.
팰린드롬을 효율적으로 판단하기 위해서는 양 끝에서 중앙으로 줄여나가면서 확인하거나, 중앙에서 양 끝으로 확장하면서 확인하는 방법이 있다.
이 문제에서는 어떤 길이의 부분 문자열이 팰린드롬일지 모르기 때문에 양 끝이 아닌, 중앙을 기준으로 확장하면서 팰린드롬인지 확인하는 방법을 사용했다.
양 끝을 기준으로 잡으면 부분 문자열로 될 수 있는 모든 길이를 고려하여 확인해야 하지만, 중앙을 기준으로 하면 딱 원래의 문자열 길이만큼만 확인하면 된다.
투 포인터 구체화
위의 그림은 투 포인터 기법으로 예시 문자열 babad의 가장 긴 팰린드롬 부분 문자열을 찾는 과정을 나타낸 그림이다.
팰린드롬인 문자열의 길이가 짝수일 수도 있으므로 중심이 2개인 경우도 고려하였다.
이렇게 하면 딱 문자열의 길이만큼만 확인하면 되고, 각 과정에서 팰린드롬인지 확인하는 시간을 고려하면 시간 복잡도는 최대 O(n^2)이 된다.
최대 문자열 길이가 1000이므로 N^2이어도 시간이 충분하다.
코드 구현
class Solution:
# 중심으로부터 확장하며 팰린드롬 찾기
def _expand_around_center(self, s: str, left: int, right: int):
while 0 <= left and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return s[left + 1 : right]
def longestPalindrome(self, s: str) -> str:
longest_palindrome = ""
for i in range(len(s)):
# 한 글자를 중심으로 하는 팰린드롬 확인 (예: "aba")
palindrome = self._expand_around_center(s, i, i)
longest_palindrome = max(palindrome, longest_palindrome, key=len)
# 두 글자를 중심으로 하는 팰린드롬 확인 (예: "abba")
palindrome = self._expand_around_center(s, i, i + 1)
longest_palindrome = max(palindrome, longest_palindrome, key=len)
return longest_palindrome문제 풀이에서 정리했던대로, 중심을 옮겨가면서 최대 길이의 팰린드롬을 찾는다.
마무리
중심으로부터 확장한다는 아이디어를 생각해내는 게 쉽지 않았다. 문제를 풀고 나서 다른 사람들의 풀이를 보니 비슷한 아이디어를 사용하는 사람들이 많았다.