Leetcode Python - 5. Longest Palindromic Substring

Leetcode #5 - Longest Palindromic Substring

이제 blind 75 leetcode를 풀어보겠습니다. https://leetcode.com/discuss/interview-question/460599/Blind-75-LeetCode-Questions

리트코드의 문제 5 ‘Longest Palindromic Substring’을 파이썬으로 풀어 보도록 하겠습니다.

discuss 참고, 포인트는 2 케이스로 나누어서 (aba, abba) 진행합니다.

전체 코드는 아래와 같습니다.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        res = ''
        for i in range(len(s)):
            tmp = self.findPalindrome(s, i, i)
            if len(res) < len(tmp):
                res = tmp
            
            tmp = self.findPalindrome(s, i, i+1)
            if len(res) < len(tmp):
                res = tmp        
        return res

            
    def findPalindrome(self, s, l, r):
        while 0<=l and r<len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        return s[l+1:r]
        

시간복잡도는

• O(n^2) : 이중 루프

공간복잡도는

• O(n) : 최악의 경우 s와 같은 크기의 res를 만듦