가장 긴 팰린드롬 부분 문자열

팰린드롬이란?

팰린드롬(palindrome)은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열(sequence of characters) 등이다.

내가 풀어본 팰린드롬 문제들

def isPalindrome(x: int) -> bool:
    """
    :type x: int
    :rtype: bool
    """
    x = str(x)
    left, right = 0, len(x) - 1
    while left >= 0 and right < len(x) and left <= right:
        left += 1
        right -= 1
        if x[left] == x[right]:
            return False
    return True

def palindrome(string):
    # 소문자에 알파벳과 숫자만 표시하기
    string = list("".join(string.lower().split()))
    for i in range(len(string)):
        if not string[i].isalnum():
            string[i] = " "
    string = "".join("".join(string).split())

    # 반 쪼개서 중간서부터 비교하기
    length = int(len(string) / 2)
    if len(string) % 2 == 0:
        return string[:length] == string[:length - 1:-1]
    else:
        return string[:length] == string[:length:-1]

def longpalindrome(s):
    # 팰린드롬 판별
    if s == s[::-1]:
        return s
    else:
        sub = []
        for n1 in range(len(s)):
            for n2 in range(n1 + 1, len(s)):
                substring = s[n1:n2 + 1]
                print(n1, n2, substring)
                # print(s[n1]==s[n2],palindrome(substring))
                if (s[n1] == s[n2] and palindrome(substring)):
                    sub.append(substring)
                else:
                    sub.append(substring[0])
        return max(sub, key=len)

longpalindrome 함수의 문제점은 두 개의 for문을 써서 시간 복잡도면에서 O(n²)이라 꽝이다. 그래도 구현은 했으니 더 빠르고 정리된 풀이들을 찾아 배워야겠다.