算法刷题目字符串
Source
Edit
History

添加最少字符使字符串整体都是回文字符串

一、题目

给定一个字符串 str，如果可以在 str 的任意位置添加字符，请返回在添加字符最少的情况下，让 str 整体都是回文字符串的一种结果

1
2
str="ABA"，str 本身就是回文串，不需要添加字符，所以返回 “ABA”
str="AB"，可以在 ‘A’ 之前添加 ‘B’，使 str 整体都是回文串，故可以返回 “BAB”。可以在 ‘B’ 之后添加 ‘A’，使 str 整体都是回文串，故也可以返回 “ABA”。总之，只要添加的字符串最少，只返回其中一种结果即可

leetcode 题目：https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/

二、分析

使用动态规划的方式，如果 str 的长度为 N，因此动态规划表是一个 N*N 的矩阵。dp[i][j] 值的含义代表子串 str[i...j] 最少添加几个字符可以使 str[i...j] 整体都是回文串。那么。如果求 dp[i][j] 的值，有如下三种情况：

  • 如果字符串 str[i...j] 只有一个字符，那么此时 str[i...j]已经是回文字符串了，此时 dp[i][j]=0
  • 如果字符串 str[i...j]只有两个字符。如果两个字符相等，那么 dp[i][j]=0。如果两个字符不相等，只用添加一个字符就可以使str[i...j]变成回文串，那么 dp[i][j]=1。
  • 如果字符串 str[i...j]多于两个字符，如果 str[i]==str[j]，那么 dp[i][j]=dp[i+1][j-1]。如果 str[i]!=str[j]，那么要让 str[i...j]整体变为回文串有两种方法。
    • 一种方法是让 str[i...j-1] 先变成回文串，然后在左边加上字符 str[j]
    • 另一种方法是让 str[i+1...j] 先变成回文串，然后在右边加上字符 str[i]。
    • 这两种方法那个代价最小就选哪个，即 dp[i][j] = min(dp[i][j-1], dp[i+1][j]) + 1

如上 i 代表的是横轴，j 代表的是纵轴。并且 i 代表字符串的左边，j 代表字符串的右边。因此 i 一定是小于等于 j 的值。

所以对于这个二维数组，我们只需要关注右上部分即可。所以如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
std::vector<std::vector<int>> get_dp(const std::string& str) {
     std::vector<std::vector<int>> dp(str.size(), std::vector<int>(str.size(), 0));
     for (int j = 1; j < str.size(); j++) {
         dp[j-1][j] = str[j-1] == str[j] ? 0 : 1;
         for (int i = j-2; i > -1; i--) {
             if (str[i] == str[j]) {
                 dp[i][j] = dp[i+1][j-1];
             } else {
                 dp[i][j] = std::min(dp[i+1][j], dp[i][j-1]) + 1;
             }
         }
     }
     return dp;
 }

我们即可求出：让字符串成为回文串的最少插入次数，此结果存储在 dp[0][str.size()-1] 位置。

接着，我们再来让字符串成为回文串，先准备一个结果字符串，这个字符串的长度为：str.size() + dp[0][str.size()-1]

使用四个变量，i，j 分别表示原始字符串的最左边和最右边；res_left 和 res_right 分别表示结果字符串的最左边和最右边。我们从左到右遍历原始字符串。每次判断 str[i] 是否等于 str[j]。

  • 如果相等，则直接在结果字符串中添加 str[i] 和 str[j]
  • 如果不相等，则需要通过 dp 数组来看 dp[i+1][j] 比较小，还是 dp[i][j-1] 比较小。选择较小的那个去添加字符。

如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <vector>
#include <string>
#include <iostream>

class Solution {
public:
    std::string get_palindromel(const std::string& str) {
        if (str.size() < 2) {
            return str;
        }
        auto dp = get_dp(str);
        std::string res(str.size() + dp[0][str.size()-1], '0');
        int i = 0;
        int j = str.size() - 1;
        int res_left = 0;
        int res_right = res.size() - 1;
        while (i <= j) {
            if (str[i] == str[j]) {
                res[res_left++] = str[i++];
                res[res_right--] = str[j--];
            } else if (dp[i][j-1] < dp[i+1][j]) {
                res[res_left++] = str[j];
                res[res_right--] = str[j--];
            } else {
                res[res_left++] = str[i];
                res[res_right--] = str[i++];
            }
        }
        return res;
    }

private:
    std::vector<std::vector<int>> get_dp(const std::string& str) {
        std::vector<std::vector<int>> dp(str.size(), std::vector<int>(str.size(), 0));
        for (int j = 1; j < str.size(); j++) {
            dp[j-1][j] = str[j-1] == str[j] ? 0 : 1;
            for (int i = j-2; i > -1; i--) {
                if (str[i] == str[j]) {
                    dp[i][j] = dp[i+1][j-1];
                } else {
                    dp[i][j] = std::min(dp[i+1][j], dp[i][j-1]) + 1;
                }
            }
        }
        return dp;
    }
};

int main() {
    Solution s;
    auto res = s.get_palindromel("AB");
    std::cout << res << std::endl;
    return 0;
}