[leetCode] Longest Palindromic Substring (Python)

✏️ 문제

leetcode.com/problems/longest-palindromic-substring/

Longest Palindromic Substring - LeetCode

✏️ 풀이

가장 긴 Palindrome 문자열을 찾는 문제이다.

(Palindrome : 앞에서부터 읽어도 뒤에서부터 읽어도 같은 문자열)

이전에 풀었던 문제는 그냥 문자열 전체가 팰린드롬인지 아닌지를 판별하는 거였어서, 단순히 앞과 뒤를 동시에 검사하면 됐었다.

이번 문제는 약간 감이 안와서 일단 brute force로 모든 sub string 을 검사하였다.

역시나 시간복잡도를 초과하였다. (ㅠㅠ)

일단 이전의 팰린드롬 문자열을 이용하여서 더 긴 문자열을 찾아야 시간 복잡도를 줄일 수 있겠다는 아이디어까지는 파악했다.

✏️ 코드

class Solution:
    
    def longestPalindrome(self, s: str) -> str:
        answer = ""

        for i in range(0,len(s)+1):
            for j in range(1, len(s)+2):
                if Solution.isPalindrome(s[i:j]):
                    if len(answer) < len(s[i:j]):
                        answer = s[i:j]
        return answer
    
    def isPalindrome(strs: str) -> bool:
        strs = list(strs)
        while len(strs) > 1:
          if strs.pop(0) != strs.pop():
              return False
        return True

isPalindrome() 함수는 전달받은 문자열의 앞과 뒤를 동시에 pop하여 반환된 문자가 같은지를 확인하여 팰린드롬인지 판별한다.

longestPalindrome() 에서는 sub-string을 isPalindrome()에 전달해주어, 길이가 가장 긴 팰린드롬을 answer에 넣어줄 수 있도록 하였다.

✏️ 다른 사람 풀이 (출처 : 파이썬 알고리즘 인터뷰)

각각 2칸, 3칸으로 된 투 포인터를 이용한다.

(팰린드롬일 수 있는 경우가 'bb'와 같은 짝수, 'bab'와 같은 홀수가 있기 때문)

이 때, 포인터 속에 들어온 문자열이 팰린드롬인 경우, 그 자리에 멈춰서 중앙을 중심으로 포인터를 확장한다. (양 끝 한 칸씩 각각 짝, 홀수로 확장됨)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # 팰린드롬 판별 및 투 포인터 확장
        def expand(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

        result = ''
        # 슬라이딩 윈도우 우측으로 이동
        for i in range(len(s) - 1):
            result = max(result,
                         expand(i, i + 1),
                         expand(i, i + 2),
                         key=len)
        return result

일단 예외처리를 해주어 입력이 한 글자이거나 문자열 전체가 팰린드롬일 경우 빠르게 리턴해주도록 처리한다.

expand() 함수를 살펴보면, 양 끝만 비교하면서(안쪽은 이미 팰린드롬 문자열이므로) 확장해나간다.

잡은 포인터가 팰린드롬이 아닌 경우에는 빈 문자열이 리턴된다.

팰린드롬인 경우에는 계속 확장해나가다가 팰린드롬이 아닌 순간 반복문을 탈출하여 리턴한다.

(s[left+1:right] 를 반환하는 이유는 마지막으로 팰린드롬이였던 문자열을 반환하기 위함)

얻은 팰린드롬 중 가장 긴 문자열을 반환한다.

✏️ 생각

ㅎㅎ풀이가 이해는 갔다만 이걸 어떻게 짠담... 막막하네 ^ㅠ^