动态规划问题(七)

一、正则表达式匹配

解法:动态规划

如果是只有小写字母，那么直接比较字符是否相同即可匹配，如果再多一个’.‘，可以用它匹配任意字符，只要对应str中的元素不为空就行了。但是多了’*'字符，它的情况有多种，涉及状态转移，因此我们用动态规划。

• 设dp[i][j]表示str前i个字符和pattern前j个字符是否匹配。（需要注意这里的i，j是长度，比对应的字符串下标要多1）

• 首先，毋庸置疑，两个空串是直接匹配，因此dp[0][0]=true。然后我们假设str字符串为空，那么pattern要怎么才能匹配空串呢？答案是利用’‘字符出现0次的特性。遍历pattern字符串，如果遇到’'意味着它前面的字符可以出现0次，要想匹配空串也只能出现0，那就相当于考虑再前一个字符是否能匹配，因此dp[0][i]=dp[0][i−2]。

• 然后分别遍历str与pattern的每个长度，开始寻找状态转移。首先考虑字符不为’‘的简单情况，只要遍历到的两个字符相等，或是pattern串中为’.‘即可匹配，因此最后一位匹配，即查看二者各自前一位是否能完成匹配，即dp[i][j]=dp[i−1][j−1]。然后考虑’'出现的情况：

pattern[j - 2] == ‘.’ || pattern[j - 2] == str[i - 1]：即pattern前一位能够多匹配一位，可以用’*'让它多出现一次或是不出现，因此有转移方程dp[i][j]=dp[i−1][j]∣∣dp[i][j−2]
不满足上述条件，只能不匹配，让前一个字符出现0次，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]表示str前i个字符和pattern前j个字符是否匹配
        vector<vector<bool> > dp(n1 + 1, vector<bool>(n2 + 1, false)); 
        //两个都为空串自然匹配
        dp[0][0] = true; 
        //初始化str为空的情况，字符串下标从1开始
        for(int i = 2; i <= n2; i++){
     
            //可以让自己前面个字符重复0次
            if(pattern[i - 1] == '*') 
                //与再前一个能够匹配空串有关
                dp[0][i] = dp[0][i - 2]; 
        }
        //遍历str每个长度
        for(int i = 1; i <= n1; i++){
     
            //遍历pattern每个长度
            for(int j = 1; j <= n2; j++){
     
                //当前字符不为*，用.去匹配或者字符直接相同
                if(pattern[j - 1] != '*' && (pattern[j - 1] == '.' || pattern[j - 1] == str[i - 1])){
     
                      dp[i][j] = dp[i - 1][j - 1];
                //当前的字符为*
                }else if(j >= 2 && pattern[j - 1] == '*'){
     
                    //若是前一位为.或者前一位可以与这个数字匹配
                    if(pattern[j - 2] == '.' || pattern[j - 2] == str[i - 1]) 
                        //转移情况
                        dp[i][j] = dp[i - 1][j] || dp[i][j - 2];  
                    else
                        //不匹配
                        dp[i][j] = dp[i][j - 2]; 
                }
            }
        }
        return dp[n1][n2];
    }
};

时间复杂度：O(mn)，其中m和n分别为字符串和模版串的长度，初始化遍历矩阵一边，状态转移遍历整个dp矩阵
空间复杂度：O(mn)，动态规划辅助数组dp的空间

二、 最长的括号子串

解法一:栈(推荐)

• 可以使用栈来记录左括号下标。
• 遍历字符串，左括号入栈，每次遇到右括号则弹出左括号的下标。
• 然后长度则更新为当前下标与栈顶下标的距离。
• 遇到不符合的括号，可能会使栈为空，因此需要使用start记录上一次结束的位置，这样用当前下标减去start即可获取长度，即得到子串。
• 循环中最后维护子串长度最大值。

class Solution {
    
public:
    int longestValidParentheses(string s) {
    
        int res = 0;
        //记录上一次连续括号结束的位置
        int start = -1; 
        stack<int> st;
        for(int i = 0; i < s.length(); i++){
    
            //左括号入栈
            if(s[i] == '(') 
                st.push(i);
            //右括号
            else{
     
                //如果右括号时栈为空，不合法，设置为结束位置
                if(st.empty()) 
                    start = i;
                else{
    
                    //弹出左括号
                    st.pop(); 
                    //栈中还有左括号，说明右括号不够，减去栈顶位置就是长度
                    if(!st.empty()) 
                        res = max(res, i - st.top());
                    //栈中没有括号，说明左右括号行号，减去上一次结束的位置就是长度
                    else 
                        res = max(res, i - start);
                }
            }
        }
        return res;
    }
};

时间复杂度：O(n)，其中n为字符串长度，遍历整个字符串
空间复杂度：O(n)，最坏全是左括号，栈的大小为n

解法二:动态规划

• 用dp[i]表示以下标为i的字符为结束点的最长合法括号长度。

• 很明显知道左括号不能做结尾，因此但是左括号都是dp[i]=0。

• 我们遍历字符串，因为第一位不管是左括号还是右括号dp数组都是0，因此跳过，后续只查看右括号的情况，右括号有两种情况：

• 情况一：
  
  如图所示，左括号隔壁是右括号，那么合法括号需要增加2，可能是这一对括号之前的基础上加，也可能这一对就是起点，因此转移公式为：dp[i]=(i>=2?dp[i−2]:0)+2

• 情况二：
  
  如图所示，与该右括号匹配的左括号不在自己旁边，而是它前一个合法序列之前，因此通过下标减去它前一个的合法序列长度即可得到最前面匹配的左括号，因此转移公式为：dp[i]=(i−dp[i−1]>1?dp[i−dp[i−1]−2]:0)+dp[i−1]+2

• 每次检查完维护最大值即可。

class Solution {
    
public:
    int longestValidParentheses(string s) {
    
        int res = 0;
        //长度为0的串，返回0
        if(s.length() == 0) 
            return res;
        //dp[i]表示以下标为i的字符为结束点的最长合法括号长度
        vector<int> dp(s.length(), 0); 
        //第一位不管是左括号还是右括号都是0，因此不用管
        for(int i = 1; i < s.length(); i++){
     
            //取到左括号记为0，有右括号才合法
            if(s[i] == ')'){
     
                //如果该右括号前一位就是左括号
                if(s[i - 1] == '(') 
                    //计数+2
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2; 
                //找到这一段连续合法括号序列前第一个左括号做匹配
                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;
            }
            //维护最大值
            res = max(res, dp[i]); 
        }
        return res;
    }
};

时间复杂度：O(n)，其中n为字符串长度，遍历一次字符串
空间复杂度：O(n)，动态规划辅助数组的长度为n