「这是我参与2022首次更文挑战的第24天，活动详情查看：2022首次更文挑战」
给你一个字符串 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 <= 500s中所有字符都是小写字母。
解题思路
本题要我们求得让字符串 s 成为回文串的最小操作次数，咋一看本题，可能会觉得无从下手。
这里我们把问题先简单化，如果只有一个字符，此时必然是回文串，操作次数为 0。
如果是两个字符，则需要判断这两个字符是否相同，如果相同，操作次数为 0，否则为 1，也就是可以以其中任何一个为中间字符，在一侧添加另一个字符。又因为本题让求最少的操作次数，所以我们自然可以想到利用动态规划来解题。
这里的输入字符串是给定的，那么影响操作次数的其实就是字符串的区间，所以我们定义二维dp dp[l][r]，l 表示区间的左边界，r 表示区间的右边界，dp[l][r] 表示使区间 l-r 内字符串成为回文串的最小操作次数。
接下来我们假设每次 l、r 分别向两端扩展一位，那么此时会有两种情况：
- 新扩展的
s[l]===s[r]，那么此时可以得出dp[l][r] = dp[l+1][r-1] - 新扩展的
s[l]!==s[r]，那么此时可以得出dp[l][r] = min(s[l+1][r],s[l][r-1])+1
所以状态转移方程为 dp[l][r] = s[l]===s[r]?dp[l+1][r-1]:min(s[l+1][r],s[l][r-1])+1
因为 dp[l] 依赖于 dp[l+1]，所以我们需要从后向前的推导每一层 dp。
又因为我们首先可以确定的小区间的值，也就是区间内只有一个字符，然后是两个字符...，所以我们内层第二维 dp 应该是从前向后推导。
代码实现
const minInsertions = (s) => { // 初始化dp const len = s.length, dp = Array(len) for (let i = 0; i < len; i++) { dp[i] = Array(len).fill(0) } // 从后向前的推导每一层 dp for (let i = len - 2; i >= 0; i--) { // 从前向后的推导当前这一层dp 也就是不断扩大区间 for (let j = i + 1; j < len; j++) { dp[i][j] = s[i] === s[j] ? dp[i + 1][j - 1] : Math.min(dp[i + 1][j], dp[i][j - 1]) + 1 } } return dp[0][len - 1] } 复制代码
滚动数组优化空间复杂度
这里我们说一下滚动数组技巧。
因为数组下标是奇偶变化的，所以这里我们对当前下标 i%2，只会得到 0,1 两种结果，而 i+1 对应的结果则刚好是当前下标对应的 0,1 中的另一个值，这样就形成了 i+1 存储在 0,i 存储在 1,i-1 存储在 0 ...
const minInsertions = (s) => { // 初始化dp const len = s.length, dp = Array(2) for (let i = 0; i < 2; i++) { dp[i] = Array(len).fill(0) } // 从后向前的推导每一层 dp for (let i = len - 2; i >= 0; i--) { const cur = i % 2, pre = !cur * 1 // 从前向后的推导当前这一层dp 也就是不断扩大区间 for (let j = i + 1; j < len; j++) { dp[cur][j] = s[i] === s[j] ? dp[pre][j - 1] : Math.min(dp[pre][j], dp[cur][j - 1]) + 1 } } return dp[0][len - 1] } 复制代码
至此我们就完成了 leetcode-1312-让字符串成为回文串的最少插入次数
如有任何问题或建议，欢迎留言讨论！👏🏻👏🏻👏🏻
