After reading this article , You can go and get the following questions ：

1312. The minimum number of inserts to make a string a palindrome string

**-----------**

Palindrome strings are the same characters read forward and backward , This kind of problem often appears in written interview .

labuladong The official account has several articles explaining palindrome , Is to judge palindrome string or find the longest palindrome string / Of subsequences ：

Calculate the longest palindrome string

Calculate the longest palindrome subsequence

This paper studies the construction of palindrome string , difficulty Hard Calculate the minimum number of times to insert a string into a palindrome string ：

Enter a string `s`

, You can insert any character anywhere in the string . If you want to put the `s`

It becomes a palindrome string , Please calculate the minimum number of insertions ？

The function signature is as follows ：

```
int minInsertions(string s);
```

Like input `s = "abcea"`

, The algorithm returns 2, Because you can give `s`

Insert 2 A character becomes a palindrome string `"abeceba"`

perhaps `"aebcbea"`

. If input `s = "aba"`

, The algorithm returns 0, because `s`

It's already a palindrome string , You don't have to insert any characters .

### Thinking analysis

First , To find the minimum number of insertions , That must be exhausting , If we use brute force algorithm to enumerate all the insertion methods , What is the complexity of time ？

You can insert any character between two characters at a time , In addition, judge whether the string is palindrome string , This time complexity is bound to explode , It's exponential .

No doubt about that. , This problem needs to be solved by using dynamic programming techniques . The previous article said , Palindrome problems are generally spread from the middle to both ends of the string , The construction of palindrome strings is similar .

** We define a two-dimensional dp Array ,dp[i][j] Is defined as follows ： The string s[i..j], At least it needs to be done dp[i][j] The second insertion can turn into palindrome string **.

We want the whole thing `s`

The minimum number of insertions , According to this definition , That is to say, to ask for `dp[0][n-1]`

Size （`n`

by `s`

The length of ）.

meanwhile ,base case It's easy to think of , When `i == j`

when `dp[i][j] = 0`

, Because when `i == j`

when `s[i..j]`

It's just a character , Itself is a palindrome string , So you don't need to do any insertion .

Next is the play of dynamic planning , Using mathematical induction to think about the state transfer equation .

PS：** I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating **. Recommended collection ,** Write the title in the order of my article **, Master all kinds of algorithm set, then put into the sea of questions, like fish .

### State transition equation

State transition is to deduce the answer to a larger problem from the answer to a small question , from base case To other states .** If we want to calculate now dp[i][j] Value , And suppose we've worked out the subproblem dp[i+1][j-1] The value of the , Can you find a way to launch dp[i][j] The value of **？

Now that we have worked out `dp[i+1][j-1]`

, I know `s[i+1..j-1]`

The minimum number of times to insert palindrome strings ,** Then we can think that s[i+1..j-1] It's already a palindrome string , So pass dp[i+1][j-1] deduction dp[i][j] The key is s[i] and s[j] These two characters **.

This score situation discussion ,** If s[i] == s[j] Words **, We don't need to do any insertion , Just know how to put

`s[i+1..j-1]`

Turn it into a palindrome string ：That's how it's translated into code ：

```
if (s[i] == s[j]) {
dp[i][j] = dp[i + 1][j - 1];
}
```

** If s[i] != s[j] Words **, It's a little bit more complicated , For example, the following situation ：

The simplest idea is , The first `s[j]`

insert `s[i]`

On the right , At the same time `s[i]`

insert `s[j]`

On the right , The string constructed in this way must be palindrome string ：

PS： Of course , hold `s[j]`

insert `s[i]`

On the left , And then put `s[i]`

insert `s[j]`

It's the same on the left , We will analyze later .

however , Does this mean that code can be written directly like this ？

```
if (s[i] != s[j]) {
// hold s[j] insert s[i] On the right , hold s[i] insert s[j] On the right
dp[i][j] = dp[i + 1][j - 1] + 2;
}
```

incorrect , For example, the following two situations , Just insert a character to make `s[i..j]`

It turns into palindrome ：

So , When `s[i] != s[j]`

when , Two brain insertions are sure to make `s[i..j]`

It becomes a palindrome string , But not necessarily the least number of inserts , The optimal insertion scheme should be broken down into the following process ：

** Step one , To make a choice , First the s[i..j-1] perhaps s[i+1..j] It becomes a palindrome string **. How to choose ？ Who becomes palindrome string insert less times , Just choose who you want .

For example, in Figure 2 , take `s[i+1..j]`

The cost of becoming a palindrome string is small , Because it is itself a palindrome string , There's no need to insert ; Empathy , For Figure 3 , take `s[i..j-1]`

It costs less to become palindrome strings .

However , If `s[i+1..j]`

and `s[i..j-1]`

None of them are palindrome strings , You need to insert at least one character to become palindrome , So choose which one is the same ：

How do I know `s[i+1..j]`

and `s[i..j-1]`

Who is cheaper to become a palindrome string ？

Look back `dp`

What is the definition of an array ,`dp[i+1][j]`

and `dp[i][j-1]`

Isn't it the price of palindrome strings ？

** Step two , According to the choice in step one , take s[i..j] It turns into palindrome **.

If you choose to put `s[i+1..j]`

It becomes a palindrome string , So in `s[i+1..j]`

Insert a character to the right `s[i]`

It's certain that `s[i..j]`

It turns into palindrome ; Empathy , If you choose to put `s[i..j-1]`

It becomes a palindrome string , stay `s[i..j-1]`

Insert a character to the left `s[j]`

It's certain that `s[i..j]`

It turns into palindrome .

So according to what I just said `dp`

The definition of array and the above analysis ,`s[i] != s[j]`

The code logic is as follows ：

```
if (s[i] != s[j]) {
// Step one is to choose the less expensive
// Step two must be inserted once
dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;
}
```

combined , The equation of state transfer is as follows ：

```
if (s[i] == s[j]) {
dp[i][j] = dp[i + 1][j - 1];
} else {
dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;
}
```

This is the core of dynamic programming algorithm , We can write the solution code directly .

PS：** I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating **. Recommended collection ,** Write the title in the order of my article **, Master all kinds of algorithm set, then put into the sea of questions, like fish .

### Code implementation

First of all to think about base case What is it? , When `i == j`

when `dp[i][j] = 0`

, Because at this time `s[i..j]`

It's a single character , Itself is a palindrome string , No need to insert ; The final answer is `dp[0][n-1]`

（`n`

Is string `s`

The length of ）. that dp table Long like this ：

And because in the state transfer equation `dp[i][j]`

and `dp[i+1][j]`

,`dp[i]-1]`

,`dp[i+1][j-1]`

Three states are related to , To ensure that every calculation `dp[i][j]`

when , All three states have been calculated , We generally choose from the bottom up , Traverse from left to right `dp`

Array ：

The complete code is as follows ：

```
int minInsertions(string s) {
int n = s.size();
// Definition ： Yes s[i..j], At least you need to insert dp[i][j] Time can become palindrome
vector<vector<int>> dp(n, vector<int>(n, 0));
// base case：i == j when dp[i][j] = 0, A single character is itself a palindrome
// dp The array has all been initialized to 0,base case Initialized
// Traverse from bottom to top
for (int i = n - 2; i >= 0; i--) {
// Traverse left to right
for (int j = i + 1; j < n; j++) {
// according to s[i] and s[j] Make a state transition
if (s[i] == s[j]) {
dp[i][j] = dp[i + 1][j - 1];
} else {
dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;
}
}
}
// according to dp Definition of array , The answer to the question is
return dp[0][n - 1];
}
```

Now the problem is solved , The complexity of time and space is O(N^2). There's also a small optimization , be aware `dp`

The state of an array is related to its adjacent state , therefore `dp`

Arrays can be compressed into one dimension ：

```
int minInsertions(string s) {
int n = s.size();
vector<int> dp(n, 0);
int temp = 0;
for (int i = n - 2; i >= 0; i--) {
// Record dp[i+1][j-1]
int pre = 0;
for (int j = i + 1; j < n; j++) {
temp = dp[j];
if (s[i] == s[j]) {
// dp[i][j] = dp[i+1][j-1];
dp[j] = pre;
} else {
// dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1;
dp[j] = =min(dp[j], dp[j - 1]) + 1;
}
pre = temp;
}
}
return dp[n - 1];
}
```

As for how this state compression works , We said earlier State compression techniques I have described in detail , It's not going to unfold here .

**＿＿＿＿＿＿＿＿＿＿＿＿＿**

my Online e-books Yes 100 Original articles , Hands with brushes 200 Daoli is the subject , Recommended collection ！ Corresponding GitHub Algorithm Repository We've got it 70k star, Welcome to mark star ！