題目出處

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

難度

Medium

題目分類

String, DP

個人範例程式碼 – 2022/8/12 三刷

class Solution:
    def longestPalindrome(self, s: str) -> str:
        ans = ""
        for i in range(len(s)):
            tmp_ans = self.is_palindrome(s, i, i)
            if len(tmp_ans) > len(ans):
                ans = tmp_ans

            tmp_ans = self.is_palindrome(s, i, i+1)
            if len(tmp_ans) > len(ans):
                ans = tmp_ans

        return ans

    def is_palindrome(self, s, start, end):
        while(0 <= start and end < len(s) and s[start] == s[end]):
            start -= 1
            end += 1

        # print(s[start+1:end])
        return s[start+1:end]

算法說明

以中間作為 palidrome 搜尋開始的起始位置，
另外寫一個驗證 palindrome 用的 function。

corner case 特殊情況處理

一起在判斷 palindrome 的 function 中做掉。

Boundary conditions/ Edge conditions 邊際情況處理

• 注意搜尋範圍 0 <= start, end < len(s)
• 注意離開迴圈後，回傳 s[start+1:end]，而不是直覺的 s[start:end+1]

個人範例程式碼 – 2022/3/28 二刷

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""

        final_ans = ""
        for index in range(len(s)):
            # odd case
            tmp_ans = self.find_max_palindrome(s, index, index)
            if len(final_ans) < len(tmp_ans):
                final_ans = tmp_ans
            # even case
            tmp_ans = self.find_max_palindrome(s, index, index+1)
            if len(final_ans) < len(tmp_ans):
                final_ans = tmp_ans

        return final_ans

    def find_max_palindrome(self, s, right_index, left_index):
        while(right_index >=0 and left_index < len(s) and s[right_index] == s[left_index]):
            right_index -= 1
            left_index += 1
        # when failed, get last ans
        return s[right_index+1:left_index]

算法說明

第二次解開始注重 coding 本身能夠自己解釋出邏輯的部分。
另外還有注重邊界檢測與 input 異常處理。

分成 odd case 與 even case 分開處理，
可以同樣以中心出發，往兩側前進 (注意邊界)

邊界檢測

檢查 for-loop, while-loop 是否有可能有越界問題

input 異常處理

主要處理以下：

• input s 為 “”，回傳 “”

個人範例程式碼 – 2021/3/31 一刷

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

向前一個個搜尋

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