[路飞]_leetcode-1312-让字符串成为回文串的最少插入次数

「这是我参与2022首次更文挑战的第24天，活动详情查看：2022首次更文挑战」

[题目地址] [B站地址]

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

解题思路

本题要我们求得让字符串 s 成为回文串的最小操作次数，咋一看本题，可能会觉得无从下手。 这里我们把问题先简单化，如果只有一个字符，此时必然是回文串，操作次数为 0。 如果是两个字符，则需要判断这两个字符是否相同，如果相同，操作次数为 0，否则为 1，也就是可以以其中任何一个为中间字符，在一侧添加另一个字符。又因为本题让求最少的操作次数，所以我们自然可以想到利用动态规划来解题。 这里的输入字符串是给定的，那么影响操作次数的其实就是字符串的区间，所以我们定义二维dp dp[l][r]，l 表示区间的左边界，r 表示区间的右边界，dp[l][r] 表示使区间 l-r 内字符串成为回文串的最小操作次数。 接下来我们假设每次 l、r 分别向两端扩展一位，那么此时会有两种情况：

1. 新扩展的 s[l]===s[r]，那么此时可以得出 dp[l][r] = dp[l+1][r-1]
2. 新扩展的 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-让字符串成为回文串的最少插入次数

如有任何问题或建议，欢迎留言讨论！👏🏻👏🏻👏🏻