力扣–讓字符串成為回文串的最少插入次數(shù)

文章目錄

• 力扣--讓字符串成為回文串的最少插入次數(shù)
• • 一、題目描述
  • 二、分析
  • 三、代碼

相關(guān)題目：

• 騰訊–構(gòu)造回文：騰訊–構(gòu)造回文

• 最長回文子串和回文鏈表：最長回文子串和回文鏈表

• 美團(tuán)/力扣(647)–回文字串：美團(tuán)/力扣(647)–回文字串

• 力扣- - 最短回文串（KMP算法）：力扣- - 最短回文串（KMP算法）

• 最長回文子序列：最長回文子序列

一、題目描述

二、分析

• 首先，要找最少的插入次數(shù)，那肯定得窮舉嘍，如果我們用暴力算法窮舉出所有插入方法，時(shí)間復(fù)雜度是多少？

• 每次都可以在兩個(gè)字符的中間插入任意一個(gè)字符，外加判斷字符串是否為回文字符串，這時(shí)間復(fù)雜度肯定爆炸，是指數(shù)級(jí)。

• 那么無疑，這個(gè)問題需要使用動(dòng)態(tài)規(guī)劃技巧來解決?；匚膯栴}一般都是從字符串的中間向兩端擴(kuò)散，構(gòu)造回文串也是類似的。

• 我們定義一個(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的長度）。

• 同時(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)行任何插入操作。

接下來就是動(dòng)態(tài)規(guī)劃的重頭戲了，利用數(shù)學(xué)歸納法思考狀態(tài)轉(zhuǎn)移方程。

• 狀態(tài)轉(zhuǎn)移就是從小規(guī)模問題的答案推導(dǎo)更大規(guī)模問題的答案，從 base case 向其他狀態(tài)推導(dǎo)嘛。

• 如果我們現(xiàn)在想計(jì)算dp[i][j]的值，而且假設(shè)我們已經(jīng)計(jì)算出了子問題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è)回文串了，所以通過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]的話，就比較麻煩了，比如下面這種情況：
  
• 最簡單的想法就是，先把s[j]插到s[i]右邊，同時(shí)把s[i]插到s[j]右邊，這樣構(gòu)造出來的字符串一定是回文串：
  
• 但是，這是不是就意味著代碼可以直接這樣寫呢？

if (s[i] != s[j]) {// 把 s[j] 插到 s[i] 右邊，把 s[i] 插到 s[j] 右邊dp[i][j] = dp[i + 1][j - 1] + 2; }

• 不對(duì)，比如說如下這兩種情況，只需要插入一個(gè)字符即可使得s[i..j]變成回文：
  

• 所以說，當(dāng)s[i] != s[j]時(shí)，無腦插入兩次肯定是可以讓s[i…j]變成回文串，但是不一定是插入次數(shù)最少的，最優(yōu)的插入方案應(yīng)該被拆解成如下流程：

• 步驟一，做選擇，先將s[i..j-1]或者s[i+1..j]變成回文串。怎么做選擇呢？誰變成回文串的插入次數(shù)少，就選誰唄。

• 比如圖二的情況，將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]誰變成回文串的代價(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; }

• 綜合起來，狀態(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; }

三、代碼

• 首先想想 base case 是什么，當(dāng)i == j時(shí)dp[i][j] = 0，因?yàn)檫@時(shí)候s[i..j]就是單個(gè)字符，本身就是回文串，不需要任何插入；最終的答案是dp[0][n-1]（n是字符串s的長度）。那么 dp table 長這樣：
  
• 又因?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ù)組：

class Solution { public:int minInsertions(string s) {if(s.empty()){return 0;}vector<vector<int>> dp(s.size(),vector<int>(s.size(),0));for(int i = s.size() - 2;i >= 0;i--){for(int j = i + 1;j < s.size();j++){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;}}}return dp[0][s.size() - 1];} };

• 優(yōu)化

class Solution { public: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 < n; 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];} };

總結(jié)

以上是生活随笔為你收集整理的力扣--让字符串成为回文串的最少插入次数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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