[python] 가장 긴 팰린드롬

https://school.programmers.co.kr/learn/courses/30/lessons/12904

---

리트코드 5번 Longest Palindrome Substring 과 똑같은 문제다

다른 점은 문자열을 리턴하는게 아니라 문자열 길이를 리턴한다는 점 빼고는 다 같다

파이썬 알고리즘 인터뷰 공부할 때 풀었던 거라 투포인터 슬라이딩도 복습했다

 

홀수개의 문자열을 체크하는 포인터와 i, i+2

짝수개의 문자열을 체크하는 포인터 i, i+1  를 계속 움직여서 처음 팰린드롬을 발견한 순간부터 양쪽의 길이를 1씩 늘려가면서 팰린드롬인지 확인하는 형태이다

 

def solution(s):
    if len(s) < 2 or s == s[::-1]:
        return len(s)
    def expand(left, right):
        while left <= right and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left+1:right]
    answer = ''
    for i in range(len(s)-1):
        answer = max(answer,
                    expand(i,i+1),
                    expand(i,i+2),
                    key=len)
    return len(answer)

 

 

더 간단하게 for문을 돌면서 [i:i+1..+2...+3...] 문자열이 팰린드롬인지 확인하고 answer를 최대값으로 갱신하는 코드로 짤 수 있지만 효율성에서 투포인터보다 못하다

def solution(s):
    if len(s) < 2 or s == s[::-1]:
        return len(s)
    answer = 1
    for i in range(len(s)):
        for j in range(i+1,len(s)+1):
            if s[i:j] and s[i:j] == s[i:j][::-1]:
                answer = max(answer, len(s[i:j]))
    return answer