1312. Minimum-Insertion-Steps-to-Make-a-String-Palindrome

difficulty: Hard

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:

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.

Method One

class Solution {
    public int minInsertions(String s) {
        // 参见 1143 516 它 和 1143 516 是一样的题目
        // 1143 是两个 string 找 最长 subsequence 
        //
        // 对于 1312, 如果我们把这个 String 反过来
        // 比如 zzaz, 反过来是 zazz, 我们找到它最长的 subsequence 的长度 k = 3，
        // 那么我们就只需要插入 N - k = 1 个就可以让  zzaz 和 zazz 相同了。
        // 论证:
        // 一个 palindrome String 和 它的 reverse string 的 最长 common subsequence 肯定是他们自己。
        // 一个 String 和 它 reverse String 的 common subsequence 肯定是 回文 palindrome 的。
        // 剩下的字母我们都可以通过在对应位置复制一份实现回文。每添加一个字符，就能减少一个不回文的字符。
        // 假设一个 string p 是 palindrome. 令 p 分成两份 p = pa + pb;
        // 现在添加一个字符 a 构成新 String 是 pa + a + pb; 
        // 记pa,pb 的reverse 是 ap, bp. ap + bp = p;
        // 那么reverse String 是 bp + a + ap. 最长 subsequence 还是 p.
        // 为了消除 a, 那么就需要在对应位置加一个 a 就行了。
        
        int N = s.length();
        int[][] dp = new int[N + 1][N + 1];
        
        for(int i = 0;i < N; i++ ) {
            for(int j = 0; j < N; j++ ) {
                int end = N - 1 - j;
                if( s.charAt(i) == s.charAt(end) ) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                }else {
                    dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j] );
                }
            }
        }
        return N - dp[N][N];
    }
}
​

以上写的可读性比较差，当年还是年轻，我也不记得这是哪年写的题了。 对于516来说，最长回文子序列, 就是找该string和它的reverse string的 最长相同子序列 LCS。 这一点可以通过观察对称性来判断。假如某string无重复字符，那么反转就会反转全部的子序列，LCS只能1. 对于1312来说，需要insertion的数量就是字符的长度，减去该LCS。

为了更清楚的阐述这一点，我写了如下的 516 的代码。

class Solution {
    public int longestPalindromeSubseq(String s) {
        int N = s.length();
        int[][] LCS = new int[N + 1][N + 1];
        StringBuilder sb = new StringBuilder(s);
        String rs = sb.reverse().toString();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (s.charAt(i) == rs.charAt(j)) {
                    LCS[i + 1][j + 1] = LCS[i][j] + 1;
                } else {
                    LCS[i + 1][j + 1] = Math.max(LCS[i + 1][j], LCS[i][j + 1]);
                }
            }
        }
        return LCS[N][N]; // 1312 返回的是 N - LCS[N][N];
    }
}