1312. Minimum Insertion Steps to Make a String Palindrome

问题:

给定一个字符串,求最少添加几个字母,能使的字符串成为回文字符串。

Example 1:
Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we don't need any insertions.

Example 2:
Input: s = "mbadm"
Output: 2
Explanation: String can be "mbdadbm" or "mdbabdm".

Example 3:
Input: s = "leetcode"
Output: 5
Explanation: Inserting 5 characters the string becomes "leetcodocteel".

Example 4:
Input: s = "g"
Output: 0

Example 5:
Input: s = "no"
Output: 1
 
Constraints:
1 <= s.length <= 500
All characters of s are lower case English letters.

  

解法:DP(动态规划)

1.确定【状态】:字符串s的

  • 第i个字符:s[i]
  • 第j个字符:s[j]

2.确定【选择】:分两种情况

  • s[i] == s[j]:
    • 前一个子串状态<不包含当前这两个字符s[i]s[j]>的需要步数:  dp[i+1][j-1]
  • s[i] != s[j]:有以下2种情况,取最小值 + 1(余下另一个字符,使之也成为回文需要补充1个字符)。
    • 字串s[i~j-1]的需要步数:dp[i][j-1] (这里余下字符s[j])
    • 字串s[i+1~j]的需要步数:dp[i+1][j] (这里余下字符s[i])

3. dp[i][j]的含义:

字符串s的第 i 个字符到第 j 个字符为止,能使得原字符串成为回文字符串,最少需要添加字符数。

4. 状态转移:

dp[i][j]=

  • (s[i] == s[j]):=前一个子串状态:dp[i+1][j-1]
  • (s[i] != s[j]):=min {
    • 上一个包含s[i]字符的状态:dp[i][j-1]
    • 上一个包含s[j]字符的状态:dp[i+1][j]    }

5. base case:

  • dp[i][i]=0:单文字子串,自己本身就是回文字符串,不需要添加任何字符。

6. 遍历顺序:

根据状态转移公式,在求得dp[i][j]之前,需先求得dp[i+1][j-1],dp[i+1][j],dp[i][j-1]

 因此需要:i:大->小,j:小->大 遍历

 

⚠️ 注意:本问题,i一定<=j,因此dp[i][j]中i>j的memory基本不会被用到。

只有在base case计算dp[i][i+1]且s[i]==s[i+1]的时候,作为★dp[i+1][j-1]被用到。应该为0。这也是在后面♻️ 优化处pre的赋值理由。

 

代码参考:

 1 class Solution {
 2 public:
 3     //status: s[i], s[j]
 4     //dp[i][j]: the min cost to make s[i,j],to a palindrome
 5     //option:
 6     //    case_1: if s[i]==s[j]: dp[i+1][j-1]
 7     //    case_2: if s[i]!=s[j]: min{
 8     //                choose s[i,j-1]: dp[i][j-1]
 9     //                choose s[i+1,j]: dp[i+1][j]
10     //             } + 1: make the left alphbet to a palindrome
11     //base case:
12     //dp[i][i]=0
13     //for: i:i+1->i, j:j-1->j
14     //     i:i--,    j:j++
15     int minInsertions(string s) {
16         int n = s.length();
17         vector<vector<int>> dp(n, vector<int>(n,0));
18         for(int i=n-1; i>=0; i--) {
19             for(int j=i+1; j<n; j++) {
20                 if(s[i] == s[j]) {
21                     dp[i][j] = dp[i+1][j-1];
22                 } else {
23                     dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1;
24                 }
25             }
26         }
27         return dp[0][n-1];
28     }
29 };

 

♻️ 优化:

空间复杂度:2维->1维

去掉 i 

压缩所有行到一行。

左下角dp[i+1][j-1]会被上面的dp[i][j-1]覆盖,因此引入变量pre,在更新dp[i][j-1]之前,保存dp[i+1][j-1]

另,在刚开始刷新每行之前,pre的初始化=0;

1312. Minimum Insertion Steps to Make a String Palindrome

 

 代码参考:

 1 class Solution {
 2 public:
 3     //status: s[i], s[j]
 4     //dp[i][j]: the min cost to make s[i,j],to a palindrome
 5     //option:
 6     //    case_1: if s[i]==s[j]: dp[i+1][j-1]
 7     //    case_2: if s[i]!=s[j]: min{
 8     //                choose s[i,j-1]: dp[i][j-1]
 9     //                choose s[i+1,j]: dp[i+1][j]
10     //             } + 1: make the left alphbet to a palindrome
11     //base case:
12     //dp[i][i]=0
13     //for: i:i+1->i, j:j-1->j
14     //     i:i--,    j:j++
15     int minInsertions(string s) {
16         int n = s.length();
17         vector<int> dp(n, 0);
18         int tmp;
19         for(int i=n-1; i>=0; i--) {
20             int pre=0;// dp[i+1][j-1]
21             for(int j=i+1; j<n; j++) {
22                 tmp = dp[j];
23                 if(s[i] == s[j]) {
24                     dp[j] = pre;
25                 } else {
26                     dp[j] = min(dp[j], dp[j-1]) + 1;
27                 }
28                 pre = tmp;
29             }
30         }
31         return dp[n-1];
32     }
33 };

 

上一篇:E2. Three Blocks Palindrome (hard version)


下一篇:Leetcode 234. Palindrome Linked List