X

LEETCODE 1312. Minimum Insertion Steps to Make a String Palindrome 解题思路分析

题目大意:

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

给你一个字符串 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.

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

View Comments (1)