化簡無所不在 用LCS的DP模型解 最長回文子序列 Longest Palindromic Subseq_LC#516

閱讀時間約 6 分鐘


題目敘述 Longest Palindromic Subsequence

給定一個字串s,請找出字串s的最長回文子序列的長度


註: 子序列 不要求一定要連續


測試範例

Example 1:

Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".

最長回文子序列是'bbbb'的長度為4

Example 2:

Input: s = "cbbd"
Output: 2
Explanation: One possible longest palindromic subsequence is "bb".

最長回文子序列是'bb'的長度為4

約束條件

Constraints:

  • 1 <= s.length <= 1000

輸入字串s的長度介於1~1000之間。

  • s consists only of lowercase English letters.

輸入字串s只會有小寫英文字母。


觀察 LCS+ s 與 逆序的s去尋找共同子序列

最長回文子序列 可以怎麼找?

回文,代表內容一定是左右對稱,而且相等。

最長回文子序列,代表一定是在s內部尋找回文的結構。


前面已經學過Longest Common Subsequebce 最長共同子序列

那我們只要把s 和 s逆序 = s[::-1] 傳入LCS最長共同子序列的演算法

就可以找到Longest Palindromic Subsequence最長回文子序列。


以s='bbbab'為例子:
LCS('bbbab', 'babbb') = 'bbbb' = LPS('bbbab)


為什麼?


因為字串s 和 s逆序找出來的共同子序列的順序,剛好一左一右,前後顛倒,內容相等

進而保障s 和 s逆序 找到的共同子序列一定是回文子序列
推理出 s 和 s逆序 最長的共同子序列也一定是最長回文子序列


字串s 和 s逆序 最長的共同子序列

= LCS(s, s[::-1]) = LPS(s) = 字串s最長回文子序列


演算法 化簡到LCS的DP模型

承接觀察點的思考,

字串s 和 s逆序找出來的共同子序列的順序,剛好一左一右,前後顛倒,內容相等

進而保障s 和 s逆序 找到的共同子序列一定是回文子序列


推理出 s 和 s逆序 最長的共同子序列也一定是最長回文子序列

那我們只要把s 和 s逆序 = s[::-1] 傳入LCS最長共同子序列的演算法

就可以找到Longest Palindromic Subsequence最長回文子序列。


程式碼 化簡到LCS的DP模型

class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
# -------------------------------------------------
# DP table
dp = {}

def LCS(i, j):

if (i, j) in dp:
# Look-up DP table
return dp[i, j]

if i == -1 or j == -1:
# Any string compare to empty string has no common sequence
dp[i, j] = 0
return 0

elif text1[i] == text2[j]:
# Current character is the same
dp[i, j] = LCS(i-1, j-1) + 1
return dp[i, j]

else:
# Current characters are different
dp[i, j] = max( LCS(i-1, j), LCS(i, j-1) )
return dp[i, j]

# -------------------------------------------------

# Original s as text1
text1 = s

# Reversed s as text2
text2 = s[::-1]

# Longest palindromic subsequence of s = Longest common subsequence(s, s[::-1])
return LCS( len(text1)-1, len(text2)-1 )

複雜度分析

令s的長度為n

時間複雜度:O(n^2)

二維DP,兩個維度的的遞迴,從字串的尾巴開始逆推回空字串,
更新最長共同(回文)子序列的長度。

空間複雜度:O(n^2)

二維DP,DP table總共紀錄O(n^2)個DP state的解。


關鍵知識點 LCS + 回文結構

利用化簡的技巧,發現彼此結構相同,把這題化簡到已經會解的Longest Common Subsequence


因為字串s 和 s逆序找出來的共同子序列的順序,剛好一左一右,前後顛倒,內容相等

進而保障s 和 s逆序 找到的共同子序列一定是回文子序列

推理出 s 和 s逆序 最長的共同子序列也一定是最長回文子序列


字串s 和 s逆序 最長的共同子序列

= LCS(s, s[::-1]) = LPS(s) = 字串s最長回文子序列


Reference

[1] Longest Palindromic Subsequence - LeetCode


回到DP特訓班目錄 和 學習路徑

58會員
345內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
發表第一個留言支持創作者!
你可能也想看
迎新活動「方格新手村」:新格友註冊加入方格子,知名日料吃到飽餐券送給你! 👉 還不是 vocus 的會員嗎?點此註冊,參與新手村活動 👈 近期站上也出現了不少新格友,為了歡迎各位的加入,「方格新手村」隨之登場! 即日起,只要是新註冊帳號於活動期間內發佈 3 則文章,就有機會抽獎獲得知名日料吃到飽餐券。原格友也可以一起同樂,我們準備了小任
Thumbnail
2024-06-21
95
順利佮人講話是無簡單的代誌我的小弟中風一年外,是出血型中風,傷著的是倒爿 pîng的頭腦,邏輯、語言等等,逐禮拜去病院做復健幾若擺,我一禮拜去恁兜一擺,佮伊同齊做一寡仔認知、講話、唸字、寫字的練習。   我想著的代誌攏共試看覓,譬喻講:自1唸到100、奇數、雙數,數字會曉加做伙無?會曉算豆仔無?三角形、圓形……會曉認無?
Thumbnail
2024-05-05
6
🍀【臼井聖火靈氣學員的上課心得-71】在靈氣點化中遇見天使的自己,感覺一切『無所畏懼的安定』悸動💗🍀🍀🍀fumi老師:❤️❤️❤ 🥰🥰🥰靈氣大師階的課程點化,是一開始會先探尋自己的內在世界,當同學看到「小王子」出現,是自己內在的形象展現,看得出來是一位充滿著赤子之心、保有童稚的溫暖療癒師。 💞💞💞在邁進靈氣大師的階段時,會是一個重新整理、重新整合自己的最棒的時機,你會看到自
Thumbnail
2024-01-26
5
節能減碳,打造無紙化綠色企業2020年開始,因新冠疫情肆虐,導致人心惶惶,自然界也沒有平靜過......。氣候變遷、海洋危機、森林大火、高溫乾旱等問題遍及全球各地,去年台灣更遭逢半世紀以來最慘的水荒!很明顯全球暖化引起的極端氣候已近在眼前。 自從歐洲工業革命以來,人類的工業活動大量燃燒煤炭、石油等化石燃料,而二氧化碳排放量也從
Thumbnail
2023-01-03
7
昨晚油價的瞬間變化以及最近的台積電,新聞製造無所不在。昨天(11月21日)的過程是這樣,原本平緩的走勢,突然傳出了下面的新聞: 美媒稱OPEC考慮下月宣布增產 遭沙烏地否認 出現增產50萬桶的新聞後,油價急殺了5美元,然後又出現了沙國澄清否認的新聞,走勢就急彈回到原本平緩的位置。
Thumbnail
2022-11-22
85
【簡筆畫 #3】中秋佳節 愉快,萬里無雲鏡九州,最團圓夜 本次作品,是以中秋節和嫦娥為設計主軸,再搭配一些可愛的人物、動物來構圖,穿插一些小飾品,就可以構出一個具有個人風格的圖畫啦~ 有興趣的朋友也可以拿起自己的畫筆,就直接畫上去了,別想太多!
Thumbnail
斷捨離不難!丹寧風、運動風、甜美風,只要搭上這件T恤就能無限變化新造型,極簡生活也能享受穿搭!妳是否也有過這種情形? 每到一個季節就會有源源不絕新單品出現,逛街看到就心動地打包帶回家,但回到家後開始面對炸滿出來的衣櫃,亦或是趕時間想搭配但困擾無法快速辨別衣服,想實施衣櫃斷捨離但每件都是心頭肉下不了手,讓總總因素困擾著...然後就又過了一個季節...。
Thumbnail
2022-03-30
0
國內疫情穩定 陳時中:無規畫9/7後降級 評估開放運動場所淋浴間中央流行疫情指揮中心日前宣布,8月24日至9月6日國內維持第2級疫情警戒,由於新冠肺炎本土疫情近日穩定,外界關注9月7日後是否有升降級考量。指揮中心指揮官陳時中今天透露,9月7日後沒有降級打算,但正在評估開放運動場所淋浴間及增加雙鐵運量。 中央流行疫情指揮中心下午召開疫情記者會,指揮中心指揮官陳時中
Thumbnail
2021-08-30
2
無法下班的接案人生30/接案人生是一件簡化生活的事!很多人會說「在家工作會分不清楚什麼時候在工作」這句話只對了一半。另一半的答案要讓接案的人來答:「接案的人沒有上班和下班的時間,生活裡有工作,而工作也是生活的一部分!」
Thumbnail
2021-05-03
7
校慶減塑強化版—師大附中「無塑」園遊會 園遊會,幾乎是每個台灣高中生生涯中難忘的一塊。當我們從課堂中學習了經濟模型、科技運用,從社團中學會了統籌規劃、分工合作,終於能在園遊會上,將所學、所思、所想付諸行動,相信對所有人都是一段難忘的回憶。 舉辦無塑園遊會(不是減塑而是「無塑」)對於任何高中都是一大難題,更別談在校生將近三千人的師大附中了
Thumbnail
迎新活動「方格新手村」:新格友註冊加入方格子,知名日料吃到飽餐券送給你! 👉 還不是 vocus 的會員嗎?點此註冊,參與新手村活動 👈 近期站上也出現了不少新格友,為了歡迎各位的加入,「方格新手村」隨之登場! 即日起,只要是新註冊帳號於活動期間內發佈 3 則文章,就有機會抽獎獲得知名日料吃到飽餐券。原格友也可以一起同樂,我們準備了小任
Thumbnail
2024-06-21
95
順利佮人講話是無簡單的代誌我的小弟中風一年外,是出血型中風,傷著的是倒爿 pîng的頭腦,邏輯、語言等等,逐禮拜去病院做復健幾若擺,我一禮拜去恁兜一擺,佮伊同齊做一寡仔認知、講話、唸字、寫字的練習。   我想著的代誌攏共試看覓,譬喻講:自1唸到100、奇數、雙數,數字會曉加做伙無?會曉算豆仔無?三角形、圓形……會曉認無?
Thumbnail
2024-05-05
6
🍀【臼井聖火靈氣學員的上課心得-71】在靈氣點化中遇見天使的自己,感覺一切『無所畏懼的安定』悸動💗🍀🍀🍀fumi老師:❤️❤️❤ 🥰🥰🥰靈氣大師階的課程點化,是一開始會先探尋自己的內在世界,當同學看到「小王子」出現,是自己內在的形象展現,看得出來是一位充滿著赤子之心、保有童稚的溫暖療癒師。 💞💞💞在邁進靈氣大師的階段時,會是一個重新整理、重新整合自己的最棒的時機,你會看到自
Thumbnail
2024-01-26
5
節能減碳,打造無紙化綠色企業2020年開始,因新冠疫情肆虐,導致人心惶惶,自然界也沒有平靜過......。氣候變遷、海洋危機、森林大火、高溫乾旱等問題遍及全球各地,去年台灣更遭逢半世紀以來最慘的水荒!很明顯全球暖化引起的極端氣候已近在眼前。 自從歐洲工業革命以來,人類的工業活動大量燃燒煤炭、石油等化石燃料,而二氧化碳排放量也從
Thumbnail
2023-01-03
7
昨晚油價的瞬間變化以及最近的台積電,新聞製造無所不在。昨天(11月21日)的過程是這樣,原本平緩的走勢,突然傳出了下面的新聞: 美媒稱OPEC考慮下月宣布增產 遭沙烏地否認 出現增產50萬桶的新聞後,油價急殺了5美元,然後又出現了沙國澄清否認的新聞,走勢就急彈回到原本平緩的位置。
Thumbnail
2022-11-22
85
【簡筆畫 #3】中秋佳節 愉快,萬里無雲鏡九州,最團圓夜 本次作品,是以中秋節和嫦娥為設計主軸,再搭配一些可愛的人物、動物來構圖,穿插一些小飾品,就可以構出一個具有個人風格的圖畫啦~ 有興趣的朋友也可以拿起自己的畫筆,就直接畫上去了,別想太多!
Thumbnail
斷捨離不難!丹寧風、運動風、甜美風,只要搭上這件T恤就能無限變化新造型,極簡生活也能享受穿搭!妳是否也有過這種情形? 每到一個季節就會有源源不絕新單品出現,逛街看到就心動地打包帶回家,但回到家後開始面對炸滿出來的衣櫃,亦或是趕時間想搭配但困擾無法快速辨別衣服,想實施衣櫃斷捨離但每件都是心頭肉下不了手,讓總總因素困擾著...然後就又過了一個季節...。
Thumbnail
2022-03-30
0
國內疫情穩定 陳時中:無規畫9/7後降級 評估開放運動場所淋浴間中央流行疫情指揮中心日前宣布,8月24日至9月6日國內維持第2級疫情警戒,由於新冠肺炎本土疫情近日穩定,外界關注9月7日後是否有升降級考量。指揮中心指揮官陳時中今天透露,9月7日後沒有降級打算,但正在評估開放運動場所淋浴間及增加雙鐵運量。 中央流行疫情指揮中心下午召開疫情記者會,指揮中心指揮官陳時中
Thumbnail
2021-08-30
2
無法下班的接案人生30/接案人生是一件簡化生活的事!很多人會說「在家工作會分不清楚什麼時候在工作」這句話只對了一半。另一半的答案要讓接案的人來答:「接案的人沒有上班和下班的時間,生活裡有工作,而工作也是生活的一部分!」
Thumbnail
2021-05-03
7
校慶減塑強化版—師大附中「無塑」園遊會 園遊會,幾乎是每個台灣高中生生涯中難忘的一塊。當我們從課堂中學習了經濟模型、科技運用,從社團中學會了統籌規劃、分工合作,終於能在園遊會上,將所學、所思、所想付諸行動,相信對所有人都是一段難忘的回憶。 舉辦無塑園遊會(不是減塑而是「無塑」)對於任何高中都是一大難題,更別談在校生將近三千人的師大附中了
Thumbnail