当前位置:网站首页>The minimum insertion times of palindrome

The minimum insertion times of palindrome

2020-11-08 19:27:04 labuladong,

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 :

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

版权声明
本文为[labuladong,]所创,转载请带上原文链接,感谢