每日一题_678.有效的括号字符串

题目：

在这里插入图片描述
题意分析：
该题是一个判断括号字符串是否合法的经典题，但和之前的是否合法字符串不同的是，这里多了一个’ * '，这个星号视作万能字符，既可以当作左括号，又可以当作右括号，也可以为空。

模拟：
首先想的方法肯定是用栈模拟了，但需要注意的是，因为星号的存在，直接一个栈模拟肯定不行，因为，当一个右括号来的时候不知道该不该用星号匹配，因为有可能这个星号在这个字符串里其实是被当作空。所以问题就出在这里的星号和括号的顺序，可以这么想，因为星号是万能的，那么在遇到左括号和星号都压栈，然后遇到右括号的时候，我们优先弹出左括号(因为要优先匹配左括号，那么星号和左括号就不能放在一个栈中，因此需要两个栈)，星号作为万能杀手锏最后在用，如果左括号没了，那么这个时候就用星号作为左括号使用，如果两个栈都为空了，那么就非法了。还有一种情况就是，字符串遍历完后，左括号栈不为空，这个时候如果还有星号，就得当作右括号使用，但是需要注意的是，星号必须出现在左括号的后面，才能正确匹配，所以为了记录相对的位置，我们的栈中，不存字符，而是存字符的位置。

class Solution {
public:

    bool checkValidString(string s) {
        if (!s.size()) return true;
        stack<int> st;
        stack<int> star;
        for (int i = 0; i < s.size();  i ++)
        {
            char ch = s[i];
            if (ch == '(') st.push(i);
            else if (ch == '*') star.push(i);
            else
            {
                if (st.size()) st.pop();
                else if (star.size()) star.pop();
                else return false;
            }
        }

        while (st.size() && star.size())
        {
            int l = st.top(), r = star.top();
            st.pop(); star.pop();
            if (l > r) return false;
        }

        return st.empty();
    }
};

动态规划：
看到这种字符串是否正确的题目，就和那种寻找最长回文子串已有，常用的西路就是线性DP。我们来看这题要求的是第0个字符到第n-1个字符是否合法，那么我们定义 dp[ i ][ j ] 表示第i个字符到第j个字符的字串是否是合法子串，那么dp[ i ][ j ] 如何由子问题得到呢？
有两种情况：

如果是 s [ i ] 和是 s[ j ] 可以构成一个括号，那么只要 dp[ i + 1][ j - 1 ]合法即可。
对于 i < k < j，将s[ i ~ j]分成两个子串，这两个子串如果都是合法，那么dp [ i ][ j ]也合法。
综上：
$\begin{cases} dp[i + 1][j - 1] \ \ \ \ \ \ if\ s[i] and s[j]构成括号对\\ dp[i][k]\ \ \ \&\& \ \ \ dp[k + 1][j]\ \ \ \ \ for \ k\in[i,j]\\ \end{cases}$

class Solution {
public:
    bool checkValidString(string s) {
        int n = s.size();
        vector<vector<bool>> dp = vector<vector<bool>>(n,vector<bool>(n,false));

        for (int i = 0; i < n; i++) {
            if (s[i] == '*') {
                dp[i][i] = true;
            }
        }

        for (int i = 1; i < n; i++) {
            char c1 = s[i - 1]; 
            char c2 = s[i];
            dp[i - 1][i] = (c1 == '(' || c1 == '*') && (c2 == ')' || c2 == '*');
        }

        for (int i = n - 3; i >= 0; i--) {
            char c1 = s[i];
            for (int j = i + 2; j < n; j++) {
                char c2 = s[j];
                if ((c1 == '(' || c1 == '*') && (c2 == ')' || c2 == '*')) {
                    dp[i][j] = dp[i + 1][j - 1];
                }
                for (int k = i; k < j && !dp[i][j]; k++) {
                    dp[i][j] = dp[i][k] && dp[k + 1][j];
                }
            }
        }
        return dp[0][n - 1];
    }
};