合縱連橫: 從 區間DP框架 理解 回文字串的本質
這篇文章，會帶著大家複習以前學過的區間DP框架，
並且以回文子字串、回文子序列的應用題與概念為核心，
貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個演算法框架。
回文字串的基本定義
s = s[::-1]
也就是說字串s的正序 和 逆序完全相同。
例如:
s = "aba" 就是一個回文字串，正序aba 逆序也是aba。兩者完全相同。
回文字串的基本結構
空字串"" 或者 單獨一個字元，肯定是回文字串。
回文字串的遞回結構
如果已知S是回文字串，那麼_S_也必定是回文字串，其中_可以是任何合法的字元。
區間DP 搭配 回文字串的定義:
DP[left, right] 代表 s[left] ~ s[right] 這個子字串是否為回文。
1 (True)代表是回文；0 (False)代表不是。
要嘛是單獨一個字元，要嘛是空字串，肯定是回文。
DP[left ,right] = 1, if left >= right
假如頭尾相等，則繼續比較內部的子字串
DP[left, right] = ( s[left] == s[right] ) and DP[left+1, right-1]
假如頭尾不相等，不可能成為回文。
DP[left, right] = 0, if s[left] != s[right]
區間DP框架在回文字串領域常用的用途
1.檢查給定的字串是否為回文字串。
2.找出最長的回文子字串。
3.找出最長的回文子序列。
接下來，我們會用這個上面這種框架，貫穿一些同類型，有關聯的題目
(請讀者、或觀眾留意上面的這種 區間DP 框架，之後的解說會反覆出現)
計算有幾個回文子字串 Palindromic Substrings
用到剛剛提到的回文字串定義，先檢查頭尾的字元是否相等。
如果相等就繼續往內檢查，直到遇到初始條件一個字元 或者 空字串為止。
如果不相等，直接返回0，因為頭尾不相等，不可能成為回文子字串。
依照區間DP框架 + 回文字串定義拓展的解題程式碼
class Solution:
def countSubstrings(self, s: str) -> int:
## Dictionary
# key: left endpoint, right endpoint
# value: 1, if s[left] ~ s[right] is palindrome.
# 0, otherwise
dp = defaultdict(int)
def check(left, right):
# Look-up dp table
if (left, right) in dp:
return dp[left, right]
# Either single character or empty string, must be palindrome
elif left >= right:
dp[left, right] = 1
# Head character is not equal to tail character, impossible to be palindrome
elif s[left] != s[right]:
dp[left, right] = 0
# Check in definition by recursion
else:
dp[left, right] = check(left+1, right-1)
return dp[left, right]
#=====================================
count = 0
# Scan each left endpoint of substring
for left in range(len(s)):
# Scan each right endpoint of substring
for right in range(left, len(s) ):
# Check s[left] ~ s[right] is palindrome or not
count += check(left, right)
return count
找出最長的回文子字串 Longest Palindromic Substring
和前一題非常類似，前一題我們是數有幾個回文子字串。
回文字串的檢查過程其實是相同的，
在檢查過程中，如果遇到更長的回文子字串，就記錄下來。
依照區間DP框架 + 回文字串定義拓展的解題程式碼
class Solution:
def longestPalindrome(self, s: str) -> str:
## Dictionary
# key: left endpoint, right endpoint
# value: 1, if s[left] ~ s[right] is palindrome.
# 0, otherwise
dp = defaultdict(bool)
def isPalindrome(left, right):
if (left, right) in dp: return dp[left, right]
if left >= right: return True
if s[left] != s[right]: return False
dp[left, right] = isPalindrome(left + 1, right - 1)
return dp[left, right]
maxLen = startIdx = 0
n = len(s)
for left in range(n):
for right in range(left, n):
# Check s[left] ~ s[right] is palindrome or not
# Record longest palindrome's start position and length if we meet
if (right-left+1) > maxLen and isPalindrome(left, right):
maxLen = right - left + 1
startIdx = left
return s[startIdx:startIdx + maxLen]
找出最長的回文子序列 Longest Palindromic Subsequence
回文子序列的檢查和回文子字串基本精神相同，只是有一個小小差異。
回文子字串要求一定要連續，回文子序列不要求一定要連續。
先檢查頭尾的字元是否相等。
如果相等就繼續往內檢查，直到遇到初始條件一個字元 或者 兩個相等的字元 為止。
如果頭尾不相等，往內縮，檢查s{left+1, right} 和 s{left, right-1}有沒有回文子序列，並且取兩者之間比較長的那一個回文子序列作為輸出答案。
依照區間DP框架 + 回文字串定義拓展的解題程式碼
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
memo = defaultdict(int)
# Find longest palindrome subsequence in interval s[left] ~ s[right]
def dp(left, right):
if (left, right) in memo:
# Look-up DP table
return memo[left, right]
if left > right :
# base case
# invalid interval, impossible to have palindrome
memo[left, right] = 0
elif left == right:
# base case:
# single character appears once
memo[left, right] = 1
elif left+1 == right and s[left] == s[right]:
# base case:
# single character appears twice continuously
memo[left, right] = 2
elif s[left] == s[right]:
# general case:
# head char = tail char, find max palindrome length of inner subsequence
memo[left, right] = dp(left+1, right-1) + 2
else:
# general case:
# head char != tail char, find max palindrome length of shorter subsequence
memo[left, right] = max( dp(left, right-1), dp(left+1, right) )
return memo[left, right]
# =============================
return dp(left=0, right=len(s)-1)
結語
好，今天一口氣介紹了最精華的部分，
通用的區間DP框架，還有相關的回文子字串、回文子序列應用題與演算法建造，
希望能幫助讀者、觀眾徹底理解它的原理，
並且能夠舉一反三，洞察其背後的本質和了解相關的應用領域！
感謝收看囉! 我們下篇文章再見~
