“This is the 24th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

[B] [C] [D]

Given a string s, each operation you can insert any character anywhere in the string.

Return the minimum number of operations needed to make S a palindrome string.

A palindrome string is a string that is identical for both forward and backward reading.

Example 1:

Input: s = "zzazz" Output: 0 Explanation: The string "zzazz" is already a palindrome string, so no insertion is required.Copy the code

Example 2:

Input: s = "mbadm" Output: 2 Description: The string can be "mbDADBM" or "mdbabdm".Copy the code

Example 3:

Input: s = "leetcode" Output: 5 Explanation: The string becomes "leetcodocteel" after 5 characters are inserted.Copy the code

Example 4:

Input: s = "g" Output: 0Copy the code

Example 5:

Input: s = "no" Output: 1Copy the code

Tip:

  • 1 <= s.length <= 500
  • sAll characters in the.

Their thinking

We need to find the minimum number of operations needed to make the string S a palindrome. Let’s simplify things a little bit. If you have only one character, it must be a palindrome string with zero operations. If the two characters are the same, check whether the two characters are the same. If they are the same, the number of operations is 0; otherwise, the number of operations is 1. That is, you can take either character as an intermediate character and add another character to one side. And since we want to minimize the number of operations, we can naturally use dynamic programming to solve this problem. The input string here is given, so the interval of the string that affects the number of operations is actually the interval of the string. Therefore, we define two-dimensional dp dp[L][r], where L represents the left boundary of the interval, r represents the right boundary of the interval, and dp[L][r] represents the minimum number of operations to make the string in the interval L-R become a palindrome string. Next, we assume that each time L and R expand by one bit, there will be two situations:

  1. The new extensions[l]===s[r], then it can be obtaineddp[l][r] = dp[l+1][r-1]
  2. The new extensions[l]! ==s[r], then it can be obtaineddp[l][r] = min(s[l+1][r],s[l][r-1])+1

So the state transition equation is dp[L][r] = S [L]=== S [r]? Dp [m + 1] [r – 1] : min (s [r], [m + 1] ‘s [l]] [r – 1) + 1 for dp [l] dependent on dp/l + 1, so we need to forward from the back of each layer is derived dp. And because we can first determine the value between cells, that is, only one character in the interval, and then two characters… , so our inner 2d DP should be derived from front to back.

Code implementation

Const minInsertions = (s) => {// Initialize dp const len = s.length, dp = Array(len) for (let I = 0; i < len; I ++) {dp[I] = Array(len).fill(0)} i >= 0; For (let j = I + 1; 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] }Copy the code

Scrolling arrays optimize spatial complexity

Let’s do a little bit of scrolling through an array. If I +1 is stored at 0, I +1 is stored at 1, I +1 is stored at 0, I +1 is stored at 1, I +1 is stored at 0, I +1 is stored at 1…

Const minInsertions = (s) => {// Initialize dp const len = s.length, dp = Array(2) for (let I = 0; i < 2; I ++) {dp[I] = Array(len).fill(0)} i >= 0; i--) { const cur = i % 2, pre = ! Cur * 1 // The current layer dp is the interval 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] }Copy the code

At this point we are done with Leetcode-1312 – the minimum number of insertions to make a string palindrome

If you have any questions or suggestions, please leave a comment! 👏 🏻 👏 🏻 👏 🏻