LeetCode 题解系列(1312)：

题目描述:

给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。

请你返回让 s 成为回文串的 最少操作次数 。

「回文串」是正读和反读都相同的字符串。

 

示例 1：

输入：s = “zzazz”
输出：0
解释：字符串 “zzazz” 已经是回文串了，所以不需要做任何插入操作。

解法一: 动态规划

1. 建立动态规划矩阵 dp[N][N]，dp[i][j]代表字符串 s[i..j]成为回文串所需要的最少插入字符数
2. 动态规划矩阵的 base case：如果只有一个元素，对应dp矩阵对角线dp[i][i]，一定是0；如果只有两个字符，对应dp矩阵dp[j-1][j]，如果 s[j-1]==s[j]，那么就是 0，否则就是 1
3. 动态规划矩阵的一般位置dp[i][j]：分两种情况：1.如果 s[i..j]中 s[i]==s[j]，那么 dp[i][j]=dp[i+1][j-1]；2.如果不相等，可能是由 s[i+1,j]的基础上在 j 的后面添加 s[i]；也可能是在 s[i,j-1]的基础上在 i 的前面添加 s[j]，两者取最小的。
4. 因为需要依赖同行左边位置，同列下边位置，左下位置，所以从第一列开始计算，并且从下往上进行计算。
5. 最终返回 dp[0][N-1] 就是结果。

时间复杂度: O(N^2); 辅助空间复杂度: O(N^2)

ass Solution {
    public int minInsertions(String s) {
        if (s == null || s.length() <= 1) {
            return 0;
        }
        int len = s.length();
        // dp[i][j]代表 s[i..j]需要添加最少的字符数量
        int[][] dp = new int[len][len];
        // 如果只有一个元素，对应dp矩阵对角线，一定是0，因为默认就是0，不用显式填充
        // 一般位置：每一列从下往上填充，因为需要同列下一行和同行上一列的值
        for (int j = 1; j < len; j++) {
            // 如果有两个元素，只有两个元素相等才是0，否则就是1
            dp[j - 1][j] = s.charAt(j - 1) == s.charAt(j) ? 0 : 1;
            for (int i = j - 2; i >= 0; i--) {
                // 如果 i 和 j 位置字符相同
                if (s.charAt(i) == s.charAt(j)) {
                    // 那么和s[i+1..j-1]所需的字符数相同
                    dp[i][j] = dp[i + 1][j - 1];
                } else {
                    // 如果不相同，有两种解决方法，两者取最小的
                    // 1.从s[i+1..j]变成s[i..j]，所需要的就是在j后面填充一个字符，这样子是dp[i+1,j]+1
                    // 2.从s[i..j-1]变成s[i..j]，所需要的就是在i前面填充一个字符，这样子是dp[i,j-1]+1
                    dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
                }
            }
        }
        // 最后的结果：dp[0][len-1]
        return dp[0][len - 1];
    }
}