문제

문자열이 주어 질때 가장 긴 팰린드롬(문자열을 반으로 접었을 때 대칭) 문자열을 부분을 출력해라!

예시

input

"babad"

output

"bab" or "aba"

input

"cbbd"

output

"bb"

풀이

book풀이1(256ms, 13.9mb)

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 - 1]:
                left -= 1
                right += 1
            return s[left + 1: right - 1]
        
        # 에러 처리 문자열 길이가 1이거나 전체 문자열이 대칭 떄 바로 리턴
        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 함수

• 문자열의 중심으로 부터 대칭 되는 값을 확인
• 검사는 문자열 길이가 홀수 일때와 짝수 일때로 나눠서 사용함.

max 함수

• max 함수에서 여러 인자들을 나열하면 그중에 최대 값을 리턴
  ex) max(2, 4, 6) --> 6
• 중심 인덱스를 하나씩 이동하면서 그 인덱스를 중앙으로 문자열을 앞뒤로 한칸 씩 증가하면서 대칭인지 검사 그 문자열 중 길이가 가장 긴 문자열을 리턴함.