[LeetCode] 5. Longest Palindromic Substring

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

---

• 가장 먼저 생각난 방법은 두 개의 포인터를 잡고 모든 부분 문자열을 순회하며 회문인지 확인하는 방법이었다.

• 이중 for문을 사용하여 두 개의 포인터의 위치를 지정하고, 두 포인터를 시작점과 끝점으로 하는 substring을 추출하여 회문인지 체크한 후, 기존에 가지고 있던 회문과 길이를 비교하여 더 긴 회문을 return하는 방식으로 코딩을 하였다.

class Solution:
    # brute_force
    def longestPalindrome(self, s: str) -> str:
        palindrom = ""
        strlen = len(s)
        if strlen < 2 or s == s[::-1]:
            return s
        for start in range(strlen):
            for end in range(start + 1, strlen + 1):
                substring = s[start:end]
                if len(substring) > len(palindrom) and substring == substring[::-1]:
                    palindrom = substring

        return palindrom

• 원하는 동작을 수행하긴 하였으나, 런타임이 상당히 길게 나온 것을 확인할 수 있었다.

---

• LeetCode에서 제공하는 힌트를 보았더니, 더 긴 회문을 찾기 위해 기존에 찾았던 회문의 앞, 뒤 문자를 비교하라는 내용이 있었다.

• 기존에 사용하던 두 포인터 중 한 포인터는 고정시키고 나머지 포인터가 문자열을 순회하며 회문을 찾는 방식에서, 문자열 가운데 임의의 지점을 잡고 두 포인터를 좌우로 한칸씩 이동하며 문자를 비교하는 방식으로 수정했다.

• 이 때, 홀수길이의 회문과 짝수길이의 회문을 둘 다 찾기 위해 포인터를 $(p, p+1)$과 $(p, p+2)$ 두 개로 나누어 for문을 돌리기로 했다.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # 길이가 2보다 짧거나 전체가 회문인 경우 바로 리턴
        if len(s) < 2 or s == s[::-1]: return s

        # 두 포인트를 잡고 한 칸씩 이동시키며 회문 판별
        def check_palindrome(p1: int, p2: int) -> str:
            while p1 >= 0 and p2 < len(s) and s[p1] == s[p2]:
                p1 -= 1
                p2 += 1
            return s[p1 + 1:p2]

        # 전체 문자열을 순회하며 회문 체크
        palindrome = ""
        for i in range(len(s) - 1):
            palindrome = max(palindrome, check_palindrome(i, i + 1), check_palindrome(i, i + 2), key=len)
    
        return palindrome

• 런타임이 훨씬 짧아진 것을 확인할 수 있었다.