[5] Longest Palindromic Substring | Leetcode Medium

🔎 問題の説明

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

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

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

🧊Pythonコード

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]