[TIL_Carrotww] 85 - 23/01/11

📝Carrotww의 코딩 기록장

🧲 python algorithm

🔍 Leetcode5_palindrome
이것도 예전에 풀었던건데 풀면서 기억이 났다
그래서 처음에는 그냥 브루트 포스로 풀면서 아닌걸 알았지만 그래도 시도해본거 그대로 시도했다.

• 처음 시도

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # palindromic 인지 확인하는 함수
        def checkpalin(word):
            if len(word) == 1:
                return True

            center_index = len(word) // 2
            if len(word) % 2 == 0:
                if word[:center_index] == ''.join(list(reversed(word[center_index:]))):
                    return True
            else:
                if word[:center_index] == ''.join(list(reversed(word[center_index+1:]))):
                    return True
            return False

        result = ''

        for i in range(len(s)):
            for x in range(len(s), i-1, -1):
                if checkpalin(s[i:x]):
                    result = max(result, s[i:x], key=lambda x: len(x))
                    continue

        return result

하나씩 확인하면서 문자열을 돌도록 작성한 알고리즘이다
역시 시간초과가 난다.

• 두 번째 풀이 - 슬라이딩 윈도우

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand(left, right):
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return s[left+1:right]

        if len(s) == 1 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=lambda x:len(x))

        return result

더 풀어야하는데...
몸이 안좋아서 그러지 못했다...ㅠ