関小君刷题记

题目大意：

让字符串成为回文串的最少插入次数

给你一个字符串 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 中所有字符都是小写字母。

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1312

解题思路分析：

leetcode中有很多变换字符串来得到回文的问题，这类题目是很明显的动态规划思路。本题也不例外。虽然这是一道Hard级别的题目，但是如果理解了之前回文题目的精髓，本题难度其实不大。

将字符串变为回文的经典做法即是，使用两个指针l和r，分别代表字符串区间的左边与右边，定义一个dp数组，dp[l][r]代表将字符串第l位到第r位区间内变换成为回文需要的次数。初始时，l在字符串的最左边，即下标为0的位置，r在最右边，即下标为字符串长度减一的位置。此时，比较两位置上的字符是否相同，如果相同的话，说明不需要变换，l向左移动一位，同时r向右移动一位。（即: dp[l][r] = dp[l+1][r-1]）

如果两个指针上的字符不相同时，我们有两种选择，l位置的字符不变，在r的右边添加一个与l位置相同的字符，添加后，l与r+1位的字符相同，接下来，l向右移动一位，r不变。即：dp[l][r] = dp[l+1][r] + 1（加一表示在r的右边添加了一个字符）。另外一种选择是，r位置的字符不变，在l的左边添加一个与r位置相同的字符，添加后，r与l-1位的字符相同，接下来，l不变，r向左移动一位。即：dp[l][r] = dp[l][r-1] + 1。这两种选择的最优解应是操作步数较少的一方，即：dp[l][r] = min( dp[l+1][r] + 1, dp[l][r-1] + 1)。

dp的结束条件为当l的下标大于r时，此时为为非法区间，可结束操作。

实现代码：

Integer[][] memo; // 记忆数组（也可理解为dp数组）
public int minInsertions(String s) {
    // 初始化记忆数组
    memo=new Integer[s.length()][s.length()];
    // 为了提高效率，将字符串转化为数组
    char[] arr = s.toCharArray();
    // 递归求解（dp过程）
    return help(arr, 0, s.length()-1);
}

int help(char[] arr, int l, int r){
    // 如果区间非法，返回0
    if(l>=r) return 0;
    // 如果记忆数组存在该区间解，直接返回
    if(memo[l][r]!=null) return memo[l][r];
    // 返回结果
    int count=0;
    // 如果两指针上的字符相同
    if(arr[l]==arr[r]){
        // 左指针加一，右指针减一，递归子问题求解
        count= help(arr,l+1,r-1);
    }else{
        // 如果两指针上的字符不同
        // 此时有2中选择，或者在左边加上一个与右指针相同的字符
        // 或者在右边加上一个与左指针相同的字符
        // 两种选择的最优解为当前结果
        count = Math.min(help(arr,l+1,r),help(arr,l,r-1))+1;
    }
    // 将当前结果保存至记忆数组
    memo[l][r]=count;
    return count;
}

本题解法执行时间为14ms。

Runtime: 14 ms, faster than 46.98% of Java online submissions for Minimum Insertion Steps to Make a String Palindrome.

Memory Usage: 37.8 MB, less than 100.00% of Java online submissions for Minimum Insertion Steps to Make a String Palindrome.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1312-minimum-insertion-steps-to-make-a-string-palindrome-解题思路分析/