leetcode 1312

问题

Given a string s. In one step you can insert any character at any index of the string.

Return the minimum number of steps to make s palindrome.

A Palindrome String is one that reads the same backward as well as forward.

Example 1:

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

Example 2:

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

Example 3:

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

Example 4:

1
2
Input: s = "g"
Output: 0

Example 5:

1
2
Input: s = "no"
Output: 1

Constraints:

  • 1 <= s.length <= 500
  • All characters of s are lower case English letters.

分析

思路1: 将 string s 反转得到 string ts ，然后求最长公共子序列，再由 s.size() 减去最长公共子序列的长度得到答案。

思路2: 先来考虑 s 是回文串的情况。当 s 是回文时，我们假设两个首尾指针 i 和 j ，分别指向 s 的头和尾，当 s[i] == s[j] 时，i++, j--; 直到不满足 i < j 的条件。于是，由此可以引申到本题的处理。在本题中声明两个首尾指针 i 和 j ，分别指向 s 的头和尾，当 s[i] == s[j] 时，i++, j--; ；当有 s[i] != s[j] 时，就需要通过插入字符来保证 s 变成一个回文。这时，插入字符的位置就有两种情况，在 i 的位置插入 s[j] 或者在 j 的位置插入 s[i]。这样问题就分解成了子问题。假设 $dp[i][j]$ 表示子串 s[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
class Solution {
public:
    int helper(const string &s, const string &t) {
        int m = s.size();
        int n = t.size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        if (s[0] == t[0]) dp[0][0] = 1;
        for (int j = 1; j < n; ++j) {
            if (s[0] == t[j]) dp[0][j] = 1;
            else dp[0][j] = dp[0][j-1];
        }
        for (int i = 1; i < m; ++i) {
            if (s[i] == t[0]) dp[i][0] = 1;
            else dp[i][0] = dp[i-1][0];
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if(s[i] == t[j])
                    dp[i][j] = dp[i-1][j-1] + 1;
                else
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[m-1][n-1];
    }

    int minInsertions(string s) {
        string ts = s;
        reverse(ts.begin(), ts.end());
        return s.size() - helper(s, ts);
    }
};

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int helper(const string &s, vector<vector<int>> &dp, int i, int j) {
        if (i >= j) return 0;
        if (dp[i][j] >= 0) return dp[i][j];
        while (i < j && s[i] == s[j]) {
            i++;
            j--;
        }
        if (i >= j) return 0;
        return dp[i][j] = 1+min(helper(s, dp, i+1, j), helper(s, dp, i, j-1));
    }
    int minInsertions(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n, -1));
        return helper(s, dp, 0, s.size()-1);
    }
};

代码3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int minInsertions(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n, -1));

        dp[0][0] = 0;
        for (int i = 1; i < n; ++i) {
            dp[i][i] = 0;
            dp[i-1][i] = s[i-1]==s[i]? 0: 1;
        }

        for (int len = 3; len <= n; ++len) {
            for (int i = 0; i < n-len+1; ++i) {
                int j = i+len-1;
                dp[i][j] = s[i]==s[j]? dp[i+1][j-1]: 1+min(dp[i+1][j], dp[i][j-1]);
            }
        }
        
        return dp[0][n-1];
    }
};