➣ Reading Time: 7 minutes

題目出處

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

⭐Python leetcode 相關文章整理⭐：
⭐Leetcode 解題紀錄⭐：難度Tag
⭐面試最經典 Top 75 題⭐：
1.【Leetcode】python - [1] Two Sum 兩數之和 個人手繪解法筆記 (只講解法重點, 內含範例程式碼)#Easy#Array #HashTable
3.【Leetcode】python - [3] Longest Substring Without Repeating Characters 個人手繪解法筆記 (只講解法重點, 內含範例程式碼) #Medium#HashTable #TwoPointers #String #SlidingWindow
5.【Leetcode】python - [5] Longest Palindromic Substring 個人手繪解法筆記 (只講解法重點, 內含範例程式碼) #Medium#String #DP
11.【Leetcode】python - [11] Container With Most Water 個人手繪解法筆記 (只講解法重點, 內含範例程式碼) #Medium#Array #TwoPointers
15.【Leetcode】python - [15] 3Sum 三數之和 個人手繪解法筆記 (只講解法重點, 內含範例程式碼) #Medium#Array #TwoPointers
48.【Leetcode】python - [48] Rotate Image 旋轉矩陣 個人手繪解法筆記與解題思考建議 (只講解法重點, 內含範例程式碼)#Medium (但我覺得很難)#Array
104.【Leetcode】python - [104] Maximum Depth of Binary Tree 個人手繪解法筆記 (只講解法重點, 內含範例程式碼) #Easy#Tree #DFS #Recursion
⭐Leetcode 小技巧⭐：
1.【Python】python 測試程式 – 利用 doctest 測試 python testcase 的優雅寫法，適用於 leetcode (doctest in function，搭配 function 的用法)
2.【Leetcode】python – 利用 doctest 測試 leetcode python testcase 的優雅寫法 (doctest in class，搭配 class 的用法)
⭐【喜歡我的文章嗎? 歡迎幫我按讚~ 讓基金會請創作者喝一杯咖啡! 】
如果喜歡我的文章，請幫我在下方【按五下Like】 (Google, Facebook 免註冊)，會由 「LikeCoin」 贊助作者鼓勵繼續創作，讀者們「只需幫忙按讚，完全不用出錢」哦!

likecoin-steps
Post Views: 166