# The minimum insertion times of palindrome

2020-11-08 19:27:04

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 ：

Judge palindrome list

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[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[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[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 ！