题目大意:
让字符串成为回文串的最少插入次数
给你一个字符串 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-解题思路分析/
View Comments (1)
个人博客坚持更新不易 留言支持下 加油 欢迎回访我家的网站