js把base64串解析成中文_回文问题终极篇:最小代价构造回文串
學(xué)算法認(rèn)準(zhǔn)?labuladong
東哥帶你手把手撕力扣?
點(diǎn)擊下方卡片即可搜索?
讀完本文,你可以去力扣完成第?1312 題「讓字符串成為回文串的最少插入次數(shù)」,難度 Hard。
回文串就是正著讀反著讀都一樣的字符串,面試筆試中經(jīng)常出現(xiàn)回文相關(guān)的題目,我們之前有好幾篇講解回文問(wèn)題的文章,是判斷回文串或者尋找最長(zhǎng)回文串/子序列的:
經(jīng)典面試題:最長(zhǎng)回文子串
子序列解題模板:最長(zhǎng)回文子序列
如何高效判斷回文單鏈表?
本文就來(lái)研究一道「構(gòu)造回文串的最小插入次數(shù)」的問(wèn)題,然后所有回文相關(guān)的問(wèn)題你都可以搞定了,如果再遇到回文算法題,就偷著樂(lè)吧~
這次的題目比較困難,讓字符串成為回文串的最少插入次數(shù):
函數(shù)簽名如下:
int?minInsertions(string?s);
比如說(shuō)輸入s = "abcea",算法返回 2,因?yàn)榭梢越os插入 2 個(gè)字符變成回文串"abeceba"或者"aebcbea"。如果輸入s = "aba",則算法返回 0,因?yàn)?code>s已經(jīng)是回文串,不用插入任何字符。
思路解析
首先,要找最少的插入次數(shù),那肯定得窮舉嘍,如果我們用暴力算法窮舉出所有插入方法,時(shí)間復(fù)雜度是多少?
每次都可以在兩個(gè)字符的中間插入任意一個(gè)字符,外加判斷字符串是否為回文字符串,這時(shí)間復(fù)雜度肯定爆炸,是指數(shù)級(jí)。
那么無(wú)疑,這個(gè)問(wèn)題需要使用動(dòng)態(tài)規(guī)劃技巧來(lái)解決。之前的文章說(shuō)過(guò),回文問(wèn)題一般都是從字符串的中間向兩端擴(kuò)散,構(gòu)造回文串也是類(lèi)似的。
我們定義一個(gè)二維的dp數(shù)組,dp[i][j]的定義如下:對(duì)字符串s[i..j],最少需要進(jìn)行dp[i][j]次插入才能變成回文串。
我們想求整個(gè)s的最少插入次數(shù),根據(jù)這個(gè)定義,也就是想求dp[0][n-1]的大小(n為s的長(zhǎng)度)。
同時(shí),base case 也很容易想到,當(dāng)i == j時(shí)dp[i][j] = 0,因?yàn)楫?dāng)i == j時(shí)s[i..j]就是一個(gè)字符,本身就是回文串,所以不需要進(jìn)行任何插入操作。
接下來(lái)就是動(dòng)態(tài)規(guī)劃的重頭戲了,利用數(shù)學(xué)歸納法思考狀態(tài)轉(zhuǎn)移方程。
狀態(tài)轉(zhuǎn)移方程
狀態(tài)轉(zhuǎn)移就是從小規(guī)模問(wèn)題的答案推導(dǎo)更大規(guī)模問(wèn)題的答案,從 base case 向其他狀態(tài)推導(dǎo)嘛。如果我們現(xiàn)在想計(jì)算dp[i][j]的值,而且假設(shè)我們已經(jīng)計(jì)算出了子問(wèn)題dp[i+1][j-1]的值了,你能不能想辦法推出dp[i][j]的值呢?
既然已經(jīng)算出dp[i+1][j-1],即知道了s[i+1..j-1]成為回文串的最小插入次數(shù),那么也就可以認(rèn)為s[i+1..j-1]已經(jīng)是一個(gè)回文串了,所以通過(guò)dp[i+1][j-1]推導(dǎo)dp[i][j]的關(guān)鍵就在于s[i]和s[j]這兩個(gè)字符。
這個(gè)得分情況討論,如果s[i] == s[j]的話,我們不需要進(jìn)行任何插入,只要知道如何把s[i+1..j-1]變成回文串即可:
翻譯成代碼就是這樣:
if?(s[i]?==?s[j])?{
????dp[i][j]?=?dp[i?+?1][j?-?1];
}
如果s[i] != s[j]的話,就比較麻煩了,比如下面這種情況:
最簡(jiǎn)單的想法就是,先把s[j]插到s[i]右邊,同時(shí)把s[i]插到s[j]右邊,這樣構(gòu)造出來(lái)的字符串一定是回文串:
PS:當(dāng)然,把s[j]插到s[i]左邊,然后把s[i]插到s[j]左邊也是一樣的,后面會(huì)分析。
但是,這是不是就意味著代碼可以直接這樣寫(xiě)呢?
if?(s[i]?!=?s[j])?{
????//?把?s[j]?插到?s[i]?右邊,把?s[i]?插到?s[j]?右邊
????dp[i][j]?=?dp[i?+?1][j?-?1]?+?2;
}
不對(duì),比如說(shuō)如下這兩種情況,只需要插入一個(gè)字符即可使得s[i..j]變成回文:
所以說(shuō),當(dāng)s[i] != s[j]時(shí),無(wú)腦插入兩次肯定是可以讓s[i..j]變成回文串,但是不一定是插入次數(shù)最少的,最優(yōu)的插入方案應(yīng)該被拆解成如下流程:
步驟一,做選擇,先將s[i..j-1]或者s[i+1..j]變成回文串。怎么做選擇呢?誰(shuí)變成回文串的插入次數(shù)少,就選誰(shuí)唄。
比如圖二的情況,將s[i+1..j]變成回文串的代價(jià)小,因?yàn)樗旧砭褪腔匚拇?#xff0c;根本不需要插入;同理,對(duì)于圖三,將s[i..j-1]變成回文串的代價(jià)更小。
然而,如果 s[i+1..j]和s[i..j-1]都不是回文串,都至少需要插入一個(gè)字符才能變成回文,所以選擇哪一個(gè)都一樣:
那我怎么知道s[i+1..j]和s[i..j-1]誰(shuí)變成回文串的代價(jià)更小呢?
回頭看看dp數(shù)組的定義是什么,dp[i+1][j]和dp[i][j-1]不就是它們變成回文串的代價(jià)么?
步驟二,根據(jù)步驟一的選擇,將s[i..j]變成回文。
如果你在步驟一中選擇把s[i+1..j]變成回文串,那么在s[i+1..j]右邊插入一個(gè)字符s[i]一定可以將s[i..j]變成回文;同理,如果在步驟一中選擇把s[i..j-1]變成回文串,在s[i..j-1]左邊插入一個(gè)字符s[j]一定可以將s[i..j]變成回文。
那么根據(jù)剛才對(duì)dp數(shù)組的定義以及以上的分析,s[i] != s[j]時(shí)的代碼邏輯如下:
if?(s[i]?!=?s[j])?{
????//?步驟一選擇代價(jià)較小的
????//?步驟二必然要進(jìn)行一次插入
????dp[i][j]?=?min(dp[i?+?1][j],?dp[i][j?-?1])?+?1;
}
綜合起來(lái),狀態(tài)轉(zhuǎn)移方程如下:
if?(s[i]?==?s[j])?{
????dp[i][j]?=?dp[i?+?1][j?-?1];
}?else?{
????dp[i][j]?=?min(dp[i?+?1][j],?dp[i][j?-?1])?+?1;
}
這就是動(dòng)態(tài)規(guī)劃算法核心,我們可以直接寫(xiě)出解法代碼了。
代碼實(shí)現(xiàn)
首先想想 base case 是什么,當(dāng)i == j時(shí)dp[i][j] = 0,因?yàn)檫@時(shí)候s[i..j]就是單個(gè)字符,本身就是回文串,不需要任何插入;最終的答案是dp[0][n-1](n是字符串s的長(zhǎng)度)。那么 dp table 長(zhǎng)這樣:
又因?yàn)闋顟B(tài)轉(zhuǎn)移方程中dp[i][j]和dp[i+1][j],dp[i]-1],dp[i+1][j-1]三個(gè)狀態(tài)有關(guān),為了保證每次計(jì)算dp[i][j]時(shí),這三個(gè)狀態(tài)都已經(jīng)被計(jì)算,我們一般選擇從下向上,從左到右遍歷dp數(shù)組:
完整代碼如下:
int?minInsertions(string?s)?{
????int?n?=?s.size();
????//?定義:對(duì) s[i..j],最少需要插入 dp[i][j]?次才能變成回文
????vector<vector<int>>?dp(n,?vector<int>(n,?0));
????// base case:i == j 時(shí) dp[i][j]?=?0,單個(gè)字符本身就是回文
????//?dp?數(shù)組已經(jīng)全部初始化為?0,base?case?已初始化
????//?從下向上遍歷
????for?(int?i?=?n?-?2;?i?>=?0;?i--)?{
????????//?從左向右遍歷
????????for?(int?j?=?i?+?1;?j?????????????//?根據(jù)?s[i]?和?s[j]?進(jìn)行狀態(tài)轉(zhuǎn)移
????????????if?(s[i]?==?s[j])?{
????????????????dp[i][j]?=?dp[i?+?1][j?-?1];
????????????}?else?{
????????????????dp[i][j]?=?min(dp[i?+?1][j],?dp[i][j?-?1])?+?1;
????????????}
????????}
????}
????//?根據(jù)?dp?數(shù)組的定義,題目要求的答案
????return?dp[0][n?-?1];
}
現(xiàn)在這道題就解決了,時(shí)間和空間復(fù)雜度都是 O(N^2)。還有一個(gè)小優(yōu)化,注意到dp數(shù)組的狀態(tài)之和它相鄰的狀態(tài)有關(guān),所以dp數(shù)組是可以壓縮成一維的:
int?minInsertions(string?s)?{
????int?n?=?s.size();
????vector<int>?dp(n,?0);
????int?temp?=?0;
????for?(int?i?=?n?-?2;?i?>=?0;?i--)?{
????????//?記錄?dp[i+1][j-1]
????????int?pre?=?0;
????????for?(int?j?=?i?+?1;?j?????????????temp?=?dp[j];
????????????if?(s[i]?==?s[j])?{
????????????????//?dp[i][j]?=?dp[i+1][j-1];
????????????????dp[j]?=?pre;
????????????}?else?{
????????????????//?dp[i][j]?=?min(dp[i+1][j],?dp[i][j-1])?+?1;
????????????????dp[j]?=?=min(dp[j],?dp[j?-?1])?+?1;
????????????}
????????????pre?=?temp;
????????}
????}
????return?dp[n?-?1];
}
至于這個(gè)狀態(tài)壓縮是怎么做的,我們前文 狀態(tài)壓縮技巧:動(dòng)態(tài)規(guī)劃的降維打擊?詳細(xì)介紹過(guò),這里就不展開(kāi)了。
往期推薦??
二叉樹(shù)的題,就那幾個(gè)框架,枯燥至極?
狀態(tài)壓縮技巧:動(dòng)態(tài)規(guī)劃的降維打擊
一個(gè)函數(shù)秒殺 2Sum 3Sum 4Sum 問(wèn)題
回溯算法和動(dòng)態(tài)規(guī)劃,到底誰(shuí)是誰(shuí)爹
東哥手寫(xiě)正則通配符算法,結(jié)構(gòu)清晰,包教包會(huì)!
_____________
學(xué)好算法全靠套路,認(rèn)準(zhǔn) labuladong 就夠了。
知乎、B站搜索:labuladong
《labuladong的算法小抄》即將出版,公眾號(hào)后臺(tái)回復(fù)關(guān)鍵詞「pdf」下載,回復(fù)「進(jìn)群」可加入刷題群。
總結(jié)
以上是生活随笔為你收集整理的js把base64串解析成中文_回文问题终极篇:最小代价构造回文串的全部?jī)?nèi)容,希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇: 侮辱我的美是哪首歌啊?
- 下一篇: 团圆的作者是谁啊?