學(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)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。