題目出處

https://leetcode.com/problems/longest-palindromic-substring/

難度

Medium

題目分類

String, DP

個人手繪解法筆記 (解法重點)

向前一個個搜尋

直覺的想，我們把每一個 index 都當作一個起點，進行各自的搜尋

單一 index 搜尋最佳解

這裡我們發現可以分成兩種 case

• case1: i-1, i, i+1 類型 (也就是有包含自己跟自己相同)
• case2: i-1, i, i+1, i+2 類型 (也就是自己跟自己+1相同)

注意：範圍的上下限，就是這題最需要細心的地方。

回收 case1, case2 結果，更新最佳答案，直到搜尋結束。

個人範例程式碼

class Solution:
    def longestPalindrome(self, s: str) -> str:
        ans = ""
        for r in range(len(s)):
            word = self.checkPalindrome(s, r)
            # print(f"word = {word}")
            if len(word) >= len(ans):
                ans = word

        return ans

    def checkPalindrome(self, s, idx):
        # case 1: i-1, i+1
        k = 0
        word1 = ""
        while(idx-k >= 0 and idx+k < len(s) and s[idx-k] == s[idx+k]):
            # record
            word1 = s[idx-k:idx+k+1]
            # print(f"idx = {idx}, k = {k}, word1 = {word1}") # debug
            # move to next
            k += 1 


        # case 2: i, i+1
        k = 0
        word2 = ""
        while(idx-k >= 0 and (idx+1)+k < len(s) and s[idx-k] == s[(idx+1)+k]):
            # record
            word2 = s[idx-k:(idx+1)+k+1]
            # print(f"idx = {idx}, k = {k}, word2 = {word2}") # debug
            # move to next
            k += 1 

        # return longest word(substring)
        if len(word1) >= len(word2):
            return word1
        else:
            return word2

Reference

https://leetcode.com/problems/longest-palindromic-substring/discuss/751188/Simple-Easy-to-Follow-Python