[5] Longest Palindromic Substring | Leetcode Medium

🔎 문제설명

Given a string s, return the longest palindromic substring in s.

Example 1

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2

Input: s = "cbbd"
Output: "bb"

제한사항

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

🧊파이썬 코드

class Solution:
    def longestPalindrome(self, s: str) -> str:
        res = ""
        for i in range(len(s)):
            res = max(self.dp(s, i, i), self.dp(s, i , i+1), res ,key = len)
        return res
        
    def dp(self, s, left, right) :
        while 0 <= left and right < len(s) and s[left] == s[right]:
            left -= 1;
            right += 1;
        return s[left + 1: right]

다른풀이

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if s == s[::-1]: 
            return s
        window,start = 1,0
        start = 0
        for i in range(1, len(s)):
            if i - window >= 0 and s[i-window:i+1] == s[i-window:i+1][::-1]:
                start = i-window
                window += 1
            elif i-window >= 1 and s[i-window-1:i+1] == s[i-window-1:i+1][::-1]:
                start = i-window-1
                window += 2
        return s[start:start+window]