This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

First, the topic overview

LeetCode 1312. The minimum number of insertions to make a string palindrome

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. Example 2: Input: s = "mbadm" Output: 2 Description: The string can be changed to "MBDADBM" or "mdbabdm". Example 3: Input: s = "leetcode" Output: 5 Description: The string becomes "leetcodocteel" after five characters are inserted. Example 4: Input: s = "g" Output: 0 Example 5: Input: s = "no" Output: 1Copy the code

Tip:

1 <= s.length <= 500 s All characters are lowercase letters.

Dry problem analysis

If you want to find the minimum number of insertions, you have to do everything.

You can insert any character between two characters at a time, plus determine whether the string is a palindrome string, and the time complexity of the string will explode exponentially.

Standard routine of dynamic planning:

  1. The first step is to be clear: state and choice
  2. Step 2 be clear:dpDefinition of an array
  3. Step 3: Think about the logic of state transitions in terms of “choices.

1. The first step is to be clear: state and choice

  1. state: “a pointeri“And” Pointersj“
  2. Choice: “Insert” or “not insert”

2. The second step is to clarify the definition of dp array

  1. dpDefinition of an array:dp[i][j], for stringss[i..j]At a minimumdp[i][j]A second insertion becomes a palindrome string.
  1. The final answer:dp[0][n - 1]The size of the (n 为 sThe length of the)
  1. base case: 当 i == jWhen,dp[i][j] = 0Because, wheni == j 时 s[i..j]Is a character, which is itself a palindrome string, so you don’t need to insert anything;

Step 3: Think about the logic of state transition in terms of “choice”

  1. If s[I] == s[j], do not need to do any insertion, just know how to turn s[I +1.. J-1] into a palindrome string

  2. If s [I]! = s[j].

Analysis step 3: state transition equation

If we want to calculate the value of dp[I][j], we can deduce the value of dp[I][j] from the subproblem dp[I + 1][j-1].

So s[I +1.. j-1] is already a palindrome string, so the key of deducing dp[I][j] from dp[I +1][j-1] lies in s[I] and S [j].

  1. If s[I] == s[j]I don’t need to insert anything, just know how to inserts[i+1..j-1]It becomes a palindrome string.

As shown in figure:

// Translate into code
if (s[i] == s[j]) {
    dp[i][j] = dp[i + 1][j - 1];
}
Copy the code
  1. If s [I]! = s[J].

When s [I]! When = s[j], two insertions will definitely make s[I..j] a palindrome string, but not necessarily the least.

As shown in figure:

Step 1: Insert s[I] to the left of s[j]

Step 2: Insert s[j] to the left of s[I]

Special circumstances:

A single character is inserted to make s[I..j] palindrome, as shown below:

In this case, s[I +1..j] or S [I.. J-1] is already a palindrome string, so there is no need to insert, just insert another one.

if(s[i] ! = s[j]) {// Step 1: Select the less expensive option
    // Step two must have an insert
    dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
}
Copy the code





Second, the idea of implementation

In the state transition equation, DP [I][j] is related to three states: DP [I + 1][j], DP [I][J-1] and DP [I + 1][J-1]. In order to ensure that the three states have been calculated every time dp[I][j] is calculated, it is generally selected from the bottom up. Traversing the DP array from left to right:

public class LeetCode_1312 {

    / / Time: O (n ^ 2), Space: O (n ^ 2), Faster - : 60.65%
    public int minInsertions(String s) {
        int n = s.length();

        // definition: for s[I..j], insert dp[I][j] at least times to become a palindrome string
        // base case: all dp arrays are initialized to 0
        int [][] dp = new int[n][n];

        // Traverse from bottom to top
        for (int i = n - 2; i >= 0; --i) {
            // Traverse from left to right
            for (int j = i + 1; j < n; ++j) {
                // State transition according to s[I] and s[j]
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j -1];
                } else {
                    dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1; }}}// Dp [0][n-1]
        return dp[0][n - 1]; }}Copy the code

Optimization:

The states of a DP array depend only on the states adjacent to it, so dp arrays can be compressed into one dimension.

public class LeetCode_1312 {

    // Time: O(n ^ 2), Space: O(n), Faster: 77.81%
    public int minInsertions(String s) {
        int n = s.length();

        int [] dp = new int[n];

        int temp = 0;
        for (int i = n - 2; i >= 0; --i) {
            / / record dp [I + 1] [1]
            int pre = 0;
            for (int j = i + 1; j < n; ++j) {
                temp = dp[j];

                if (s.charAt(i) == s.charAt(j)) {
                    // dp[i][j] = dp[i+1][j-1];
                    dp[j] = pre;
                } else {
                    // dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
                    dp[j] = Math.min(dp[j], dp[j - 1]) + 1; } pre = temp; }}return dp[n - 1]; }}Copy the code