宝宝也能看懂的 leetcode 周赛 - 170 - 4
2020/1/11 5:17:14
本文主要是介绍宝宝也能看懂的 leetcode 周赛 - 170 - 4,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1312. 让字符串成为回文串的最少插入次数
Hi 大家好,我是张小猪。欢迎来到『宝宝也能看懂』系列之 leetcode 周赛题解。
这里是第 170 期的第 4 题,也是题目列表中的第 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
中所有字符都是小写字母。
官方难度
HARD
解决思路
一看到回文字符串,脑中第一反应就是那个马拉车算法,然后瞬间就不想做这道题了,小猪闹脾气,哼 T_T
不过冷静下来之后还是先仔细看一下题的内容。题目要求为给定一个字符串,我们可以向里面任意位置插入任何字符,最终要使得该字符串变成一个回文字符串。需要得到这个最小的被插入的字符数量。
其实我的第一反应是要不要找到当前的最长回文子字符串,然后基于它来判断两边的差异从而得到结果。可是这样会有一个问题,那就是基于最长回文子字符串作为中点来进行填充,真的是最优解么?对于这个疑问我们可以看一下这个例子。
对于 "abccdec" 这个字符串,我们可以得到最长的回文子字符串是 "cc"。如果我们基于它作为中点,那么由于左右完全不一样,需要 5 个字符来进行补齐,例如 "abcedccdecba"。但其实我们可以做到只用 4 个字符进行补齐,即 "abcedcdecba"。这是由于对于奇数长度的字符串,中点其实不需要进行补齐,而我们也利用了左右一对匹配的 "c" 字符,所以可以减少一个补齐字符的需求。
那么我们尝试换一个思路,回到这个字符串本身的特性。如果它最后要变成一个回文字符串,那么它最终的最左侧和最右侧的字符一定要是相同的。所以反推回来,如果当前最左侧和最右侧的字符一样,便可继续遍历。但是如果不一样呢?这时候我们可以进行填补。可是填补的方式有两种:
- 我们可以在左侧填补一个最右侧的字符,这时候左侧可以继续向前遍历。
- 我们可以在右侧填补一个最左侧的字符,这时候右侧可以继续向前遍历。
对于这两种填补方式,它们的填补消耗都是 1 个字符,我们也无法确定哪一种是最优解。所以只有继续推导,直到最终遍历完成后便可得到全局最优解。
动态规划
基于上述思路,我们不难想到这里可以利用动态规划的方式来进行实现,或者说动态规划是对于这种思路方式的一种比较不错的实现。
那么什么是动态规划呢?详细的内容还是期待新坑吧,哈哈哈哈,小猪这里就不展开啦。我们这里先基于这道题目的内容进行分析和说明就好了。
如上述思路中提到的内容,如果我们想知道区间 [left, right]
范围里的最优解,那么可能存在两种情况,即 s[left] === s[right]
或者 s[left] !== s[right]
。针对这两种情况,我们可以得到两种对应的结果,即 0 + [left + 1, right - 1]
和 1 + min([left + 1, right], [left, right - 1])
。如果写成一个递推公式的话可以是:
f(left, right) = s[left] === s[right] ? f(left + 1, right - 1) : 1 + min(f(left + 1, right), f(left, right - 1))
那么接下来按照动态规划的惯例,我们使用一个数组来记录递推的过程和中间值。具体流程如下:
- 申明一个二维数组。
- 初始化长度为 1 时候的每个字符串所需要的开销,即 0,因为一个字符自身就是回文字符串。
- 根据上面的递推公式,逐层的推出每一层的值。
- 最终取出
[0, s.length - 1]
对应的值就是我们的结果。
根据上述流程,我们可以实现类似下面的代码:
const minInsertions = s => { const LEN = s.length; const dp = []; for (let i = 0; i < LEN; ++i) { dp[i] = new Uint16Array(LEN); dp[i][i + 1] = s[i] === s[i + 1] ? 0 : 1; } for (let i = 2; i < s.length; ++i) { for (j = 0; j < s.length - i; ++j) { dp[j][j + i] = s[j] === s[j + i] ? dp[j + 1][j + i - 1] : 1 + Math.min(dp[j + 1][j + i], dp[j][j + i - 1]); } } return dp[0][s.length - 1]; };
优化
上面的代码时间复杂度 O(n^2),空间复杂度也是 O(n^2)。那么其实按照经验,我们可以尝试一下把空间复杂度压缩到 O(n),即不是用二维数组,只是用一维数组来记录递推的中间值。
不过这里要注意的是,由于我们无法保存所有历史的中间值,所以我们的遍历递推方向做出了一点调整。具体的代码如下:
const minInsertions = s => { const LEN = s.length; const dp = new Uint16Array(LEN); for (let i = LEN - 2; i >= 0; i--) { let prev = 0; for (let j = i; j < LEN; j++) { const tmp = dp[j]; dp[j] = s[i] == s[j] ? prev : 1 + Math.min(dp[j], dp[j - 1]); prev = tmp; } } return dp[s.length - 1]; };
这段代码跑出了 60ms,暂时 beats 100%。
总结
这道题的风格可能更偏向于科班一点,特别是其中关于动态规划的部分,包含着满满的套路感。不过我觉得这里面比较重要的部分在与,整个推导过程中前者和后者的关系,也就是如何基于当前值衍生出下一个值。一旦有了这个推导公式,我们便能较为容易的写出对应的代码实现了。
相关链接
这篇关于宝宝也能看懂的 leetcode 周赛 - 170 - 4的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-21动态面包屑教程:新手入门指南
- 2024-12-21动态主题处理教程:新手必读指南
- 2024-12-21富文本编辑器教程:新手入门指南
- 2024-12-21前端项目部署教程:从零开始的全面指南
- 2024-12-21拖拽表格教程:轻松入门指南
- 2024-12-21Element-Plus教程:新手入门与实战指南
- 2024-12-21TagsView标签栏导航教程:轻松掌握标签栏导航
- 2024-12-21动态表格实战:新手入门教程
- 2024-12-21动态菜单项实战:一步步教你实现动态菜单项
- 2024-12-21动态面包屑实战:新手教程