문제 링크

1️⃣ 내 풀이

🔹 두 글자 겹치면 짝수 길이인 팰린드롬수인지 확인

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) <= 1:
            return s

        def look_odd(s, idx):
            i = 1
            res = ''
            while idx-i >= 0 and idx+i < len(s):
                if s[idx-i] == s[idx+i]:
                    res = s[idx-i:idx+i+1]
                    i+=1
                else:
                    break
            return res

        def look_even(s, idx):
            i = 1
            res = ''
            left, right = idx-1, idx
            while left >= 0 and right < len(s):
                if s[left] == s[right]:
                    res = s[left:right+1]
                    left -= 1
                    right += 1
                else:
                    break
            return res

        prev = '가'
        ans = ''
        for idx in range(len(s)):
            ans = max(look_odd(s, idx), ans, key=len)
            if prev == s[idx]:
                ans = max(ans, s[idx-1: idx+1], look_even(s, idx), key = len)
            prev = s[idx]
            
        return max(ans, s[0], key = len)

연속 두 글자가 겹치는지 확인하는 로직도 그냥 팰린드롬인지 확인하는 함수 안에서 수행되면 될 일이었다.

🔹 모범 풀이를 읽고 나서 다시 풀어본 내 풀이

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s)<=1 or s == s[::-1]:
            return s

        def expand(left, right):
            res = ''
            for i in range(0, len(s)-1):
                start = i+left
                end = i + right
                while start>=0 and end<len(s) and s[start] == s[end]:
                    res = max(res, s[start: end+1], key=len)
                    start-=1
                    end+=1
                res = max(res, s[start+1: end], key=len)
            
            return res
                
        return max('', expand(0,0), expand(0,1), key=len)

2️⃣ 모범 풀이

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

💡 파이썬 문자열 슬라이싱은 범위가 넘어가도 에러가 나지 않는다.
그냥 가능한 범위까지만 잘라서 반환한다.
시작 위치 자체가 문자열 밖이라면 빈 문자열을 반환한다.

근데 인덱싱의 경우엔 다르다.
s = 'abcdefg'
s[10] → IndexError 발생
s[10:20] → 에러 없음. ''반환

다음에 더 공부해 볼 만한 내용 : Manacher Algorithm
위 풀이들에서는 시간 복잡도 O(n^2)이 나오지만,
이 Manacher Algorithm을 활용하면 O(n)에 풀 수 있다.😲
이 알고리즘은 이미 구한 팰린드롬 정보를 재활용하고
문자열을 한번만 스캔하면서 모든 팰린드롬 길이를 계산한다.