Dynamic programming problem (VII)

One 、 Regular Expression Matching

solution : Dynamic programming

If it's only lowercase , Then directly compare whether the characters are the same to match , If there is one more ’.‘, You can use it to match any character , As long as it corresponds to str If the element in is not empty . But more ’*' character , There are many situations , Involving state transition , So we use dynamic programming .

• set up dp[i][j] Express str front i Characters and pattern front j Whether characters match .（ You need to pay attention to the i,j It's length. , More than the corresponding string subscripts 1）

• First , Beyond all doubt , Two empty strings are directly matched , therefore dp[0][0]=true. Then we assume str The string is empty , that pattern How can I match an empty string ？ The answer is to use ’‘ The character appears 0 Secondary characteristics . Traverse pattern character string , If you encounter ’' It means that the characters in front of it can appear 0 Time , To match an empty string, there can only be 0, That's equivalent to considering whether the previous character can match , therefore dp[0][i]=dp[0][i−2].

• Then traverse str And pattern Each length of , Start looking for state transitions . First, consider that the character is not ’‘ Simple situation of , As long as the two characters traversed are equal , or pattern In the string is ’.‘ To match , So the last bit matches , That is, check whether the previous one of the two can complete the matching , namely dp[i][j]=dp[i−1][j−1]. Then consider ’' What happened ：

pattern[j - 2] == ‘.’ || pattern[j - 2] == str[i - 1]： namely pattern The previous one can match one more , It can be used ’*' Let it appear one more time or not , So there's a transfer equation dp[i][j]=dp[i−1][j]∣∣dp[i][j−2]
Not meeting the above conditions , Can only not match , Let the previous character appear 0 Time ,dp[i][j]=dp[i][j−2].

class Solution {
    
public:
    bool match(string str, string pattern) {
    
        int n1 = str.length();
        int n2 = pattern.length();
        //dp[i][j] Express str front i Characters and pattern front j Whether characters match 
        vector<vector<bool> > dp(n1 + 1, vector<bool>(n2 + 1, false)); 
        // Both are empty strings and naturally match 
        dp[0][0] = true; 
        // initialization str Empty situation , String subscript from 1 Start 
        for(int i = 2; i <= n2; i++){
     
            // You can repeat the first character of yourself 0 Time 
            if(pattern[i - 1] == '*') 
                // It is related to the previous one that can match the empty string 
                dp[0][i] = dp[0][i - 2]; 
        }
        // Traverse str Each length 
        for(int i = 1; i <= n1; i++){
     
            // Traverse pattern Each length 
            for(int j = 1; j <= n2; j++){
     
                // The current character is not *, use . To match or match characters directly 
                if(pattern[j - 1] != '*' && (pattern[j - 1] == '.' || pattern[j - 1] == str[i - 1])){
     
                      dp[i][j] = dp[i - 1][j - 1];
                // The current character is *
                }else if(j >= 2 && pattern[j - 1] == '*'){
     
                    // If the previous one is . Or the previous digit can match this number 
                    if(pattern[j - 2] == '.' || pattern[j - 2] == str[i - 1]) 
                        // Transfer situation 
                        dp[i][j] = dp[i - 1][j] || dp[i][j - 2];  
                    else
                        // Mismatch 
                        dp[i][j] = dp[i][j - 2]; 
                }
            }
        }
        return dp[n1][n2];
    }
};

Time complexity ：O(mn), among m and n Respectively, the length of string and template string , Initialize ergodic matrix side , The state transition traverses the entire dp matrix
Spatial complexity ：O(mn), Array aided dynamic programming dp Space

Two 、 Longest bracket substring

Solution 1 : Stack ( recommend )

• You can use the stack to record the left parenthesis subscript .
• Traversal string , Left bracket in stack , Each time the right bracket is encountered, the subscript of the left bracket will pop up .
• Then the length is updated to the distance between the current subscript and the subscript at the top of the stack .
• Inconsistent parentheses encountered , May make the stack empty , So you need to use start Record the last ending position , This subtracts from the current subscript start You can get the length , The substring is obtained .
• The maximum length of the last maintained substring in the loop .

class Solution {
    
public:
    int longestValidParentheses(string s) {
    
        int res = 0;
        // Record the last position where consecutive parentheses ended 
        int start = -1; 
        stack<int> st;
        for(int i = 0; i < s.length(); i++){
    
            // Left bracket in stack 
            if(s[i] == '(') 
                st.push(i);
            // Right bracket 
            else{
     
                // If the stack is empty when closing the parenthesis , illegal , Set to end position 
                if(st.empty()) 
                    start = i;
                else{
    
                    // Pop up the left bracket 
                    st.pop(); 
                    // There are also left parentheses in the stack , The right bracket is not enough , Subtracting the top of the stack is the length 
                    if(!st.empty()) 
                        res = max(res, i - st.top());
                    // There are no parentheses in the stack , Explain the line numbers in the left and right brackets , Subtracting the last ending position is the length 
                    else 
                        res = max(res, i - start);
                }
            }
        }
        return res;
    }
};

Time complexity ：O(n), among n Is the length of a string , Traversing the entire string
Spatial complexity ：O(n), At worst, it's all left parentheses , The stack size is n

Solution 2 : Dynamic programming

• use dp[i] Indicates that the following is marked as i The character of is the longest legal bracket length of the end point .

• It's obvious that the left parenthesis can't be the end , So the left parentheses are all dp[i]=0.

• We traverse the string , Because the first place is either the left bracket or the right bracket dp Arrays are all 0, So skip , We will only look at the right parenthesis later , There are two cases of closing parentheses ：

• Situation 1 ：
  
  As shown in the figure , Next to the left bracket is the right bracket , Then the legal brackets need to be added 2, It is possible to add... On the basis before this pair of parentheses , Maybe this pair is the starting point , So the transfer formula is ：dp[i]=(i>=2?dp[i−2]:0)+2

• Situation two ：
  
  As shown in the figure , The left bracket that matches the right bracket is not next to itself , But before the legal sequence before it , Therefore, the first matching left parenthesis can be obtained by subtracting the legal sequence length of the previous one from the subscript , So the transfer formula is ：dp[i]=(i−dp[i−1]>1?dp[i−dp[i−1]−2]:0)+dp[i−1]+2

• Maintain the maximum value after each inspection .

class Solution {
    
public:
    int longestValidParentheses(string s) {
    
        int res = 0;
        // The length is 0 String of , return 0
        if(s.length() == 0) 
            return res;
        //dp[i] Indicates that the following is marked as i The character of is the longest legal bracket length of the end point 
        vector<int> dp(s.length(), 0); 
        // First, whether the left bracket or the right bracket is 0, So don't worry 
        for(int i = 1; i < s.length(); i++){
     
            // Take the left bracket and mark it as 0, It is legal to have a right parenthesis 
            if(s[i] == ')'){
     
                // If the previous position of the right bracket is the left bracket 
                if(s[i - 1] == '(') 
                    // Count +2
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2; 
                // Find the first left parenthesis before this sequence of consecutive legal parentheses to match 
                else if(i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') 
                    dp[i] = (i - dp[i - 1] > 1 ? dp[i - dp[i - 1] - 2] : 0) + dp[i - 1] + 2;
            }
            // Maintenance maximum 
            res = max(res, dp[i]); 
        }
        return res;
    }
};

Time complexity ：O(n), among n Is the length of a string , Traverse the string once
Spatial complexity ：O(n), The length of dynamic programming auxiliary array is n