[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.
  • 🧊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]