內容目錄
題目出處
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
★留個言吧!內容有誤或想要補充也歡迎與我討論!