LeetCode 题解 | 1312. 让字符串成为回文串的最少插入次数

我就是我 2023-06-30 10:43 22阅读 0赞

点击上方蓝字设为星标![format_png][]

下面开始今天的学习～

![format_png 1][]

今天分享的题目来源于 LeetCode 第 1312 题：让字符串成为回文串的最少插入次数。

### 题目描述 ###

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

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

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

**示例 1：**

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

**示例 2：**

输入：s = "mbadm"
    输出：2
    解释：字符串可变为 "mbdadbm" 或者 "mdbabdm" 。

**示例 3：**

输入：s = "leetcode"
    输出：5
    解释：插入 5 个字符后字符串变为 "leetcodocteel" 。

**示例 4：**

输入：s = "g"
    输出：0

**示例 5：**

输入：s = "no"
    输出：1

**提示：**

*  1 <= s.length <= 500
 *  s 中所有字符都是小写字母。

### 题目解析 ###

题目给定一个字符串，问最少插入多少个字符可以使得这个字符串变成回文串。

拿到这个问题，我们可以先回顾一下，如何判断一个字符串是回文串？

最直接的做法就是**相向双指针**。

这道题我们也可以参考这样的思路，如果头尾的两个指针指向的字符相等，那我们就同时相向移动两个指针，**但是如果头尾的两个指针指向的字符不相等，我们就需要插入字符了**。

这里有两个选择，在头指针的前方插入尾指针指向的字符，移动尾指针；还有就是在尾指针的后方插入头指针指向的字符，移动头指针。

每当头尾指针指向的字符不相同的时候，我们都有这两种选择，最终，我们要求使得区间 `[0, n]` 是回文的最小插入次数，我们可以定义，`dp[i][j]` 表示的是使得区间 `[i, j]` 是回文的最小插入次数，我们也可以得出递推方程：

s[i] == s[j]: dp[i][j] = dp[i + 1][j - 1]
    s[i] != s[j]: dp[i][j] = Math.min(dp[i][j - 1], d[i + 1][j]) + 1

推荐使用记忆化搜索的实现方式，这样可以减少不必要的考虑。

### 参考代码 ###

public int minInsertions(String s) {
        int[][] memo = new int[s.length()][s.length()];
    
        for (int i = 0; i < s.length(); ++i) {
            Arrays.fill(memo[i], Integer.MAX_VALUE);
        }
    
        return helper(s.toCharArray(), 0, s.length() - 1, memo);
    }
    
    private int helper(char[] sArr, int left, int right, int[][] memo) {
        if (left >= right) {
            return 0;
        }
    
        if (memo[left][right] != Integer.MAX_VALUE) {
            return memo[left][right];
        }
    
        if (sArr[left] == sArr[right]) {
            return memo[left][right] = helper(sArr, left + 1, right - 1, memo);
        }
    
        return memo[left][right] = Math.min(helper(sArr, left + 1, right, memo),
                                            helper(sArr, left, right - 1, memo)) + 1;
    
    }

![format_png 2][]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9pY0hvZXJLTzNOakxHa0wzSmljWnh6WlVsTVBXYU9FVXRpYVZ5RHQ1QU9hSUpOa0xhbHRYT1lSaWFHU2J5aWJneFFzVkxSYXo5SnhmTjZLVkJtU05GYkZlNkx3LzY0MA?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9taWFabTA1NHZVaWJ1Mlo1T0d1SXpidXdUaWFpYmlhNWxNU3pJM29iS1B4SDlLeGtTeTdQM3NkNjlpY0dUR3kxVGVXUXIzTjIxUVNjcnJpYmFIRGJYRmJrd1lnOXcvNjQw?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVEzMENBYUxzOVhEMEpwQXNxYm1HbDNnaWI5bTBtZDFyY0pnTmNpYmN1RHNzTmxEc2liTkZyNDBNOWdIaGFnSklVR2ljMkp4M2lhS0FOb1NQdy82NDA?x-oss-process=image/format,png