【lc】678-有效括号模式

输入一个字符串，仅有3种字符构成
(, *, ),
其中 * 可以代表左括号或右括号，或空字符
请判断字符串是否是有效的括号串，注意，空串属于有效

---

想法：
这道题比较有意思，首先会想到最基础的判断有效括号。我们会用一个栈，遇到左括号入栈，遇到右括号出栈，比较容易做出来。
加上星号以后，让问题复杂了一些。在这里提供三种解法。

---

法1 动态规划
dp的思想，其实也就是分治的思想。区别只是自上而下还是自下而上。
那么我们会想：一个问题是否可以被拆解成同一个规模更小的问题，当规模达到最小时，问题的解是确定的。
反方向来说，一个模式是否可以被扩展，从而得到更大问题的解。

不管从哪个方向来说，都蕴藏着dp的两个关键问题

1. base case，即规模最小时的确定情况
2. 状态转移，即不同尺度的问题直接如何相互利用，他们的确定关系是什么

我们从dp的2个关键来看这道题，
1.基本情况，只有一个字符的情况，当为*时合法
2.只有2个字符的情况，4种情况合法
3.有了以上2个base cases，考虑状态的转移，一个较大的合法串，只有以下2种拆解形式
4.（【】） 即它的最外层是括号，注意可被 * 替换
5.【】【】可以从中间拆为2个合法串

在笔试中想到的是自顶向下，但当时的做法并不完善，后经过改良。

class Solution {
public:
  /**
   * @param s string字符串 
   * @return bool布尔型
   */
  using vi = vector<int>;
  vector<vi> dp;
  /**
   * 0 not visited
   * 1 bad
   * 2 good
   * 也就是备忘录方法，这种解法会超时
  */
  bool getRes(string& s, int l, int r) {
    if (dp[l][r] > 0) {
      return dp[l][r] == 1 ? false : true;
    }
    if (l == r) {
      if (s[l] == '*') {
        dp[l][l] = 2;
        return true;
      } else {
        dp[l][l] = 1;
        return false;
      }
    }
    if (l == r - 1) {
      if (s[l] == '(' || s[l] == '*') {
        if (s[r] == ')' || s[r] == '*') {
          dp[l][l] = 2;
          return true;
        }
      }
      dp[l][l] = 1;
      return false;
    }

    bool first = false;
    if (s[l] == '(' || s[l] == '*') {
      if (s[r] == ')' || s[r] == '*') {
        first = true;
      }
    }
    first = first && getRes(s, l + 1, r - 1);
    if (first) {
      dp[l][r] = 2;
        return true;
    }
    for (int i = l; i < r; i++) {
      bool res = getRes(s, l, i) && getRes(s, i + 1, r);
      if (res) {
        dp[l][r] = 2;
        return true;
      }
    }
    dp[l][l] = 1;
    return false;
  }

  bool checkValidString(string s) {
    int len = s.size();
    dp = vector<vi>(len, vi(len));
    return getRes(s, 0, len - 1);
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

自底向上的方法

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];
    }
};

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/valid-parenthesis-string/solution/you-xiao-de-gua-hao-zi-fu-chuan-by-leetc-osi3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

时间on3，空间on2

---

法2 栈
是基础栈的扩展版本
有星号的存在，我们需要2个栈，一个放左括号，一个放 *
这两种符号，遇到直接入栈
遇到右括号，可以消掉栈中元素，优先消掉左括号，没有可用时消掉 *
2个栈都为空则为false

遍历结束后，栈可能不为空，此时需要将每个左括号与 * 匹配。注意index大小，左括号必须在 * 左侧
否则false
若左括号有剩余 false
若只剩 * true

class Solution {
public:
    bool checkValidString(string s) {
        stack<int> leftStack;
        stack<int> asteriskStack;
        int n = s.size();

        for (int i = 0; i < n; i++) {
            char c = s[i];
            if (c == '(') {
                leftStack.push(i);
            } else if (c == '*') {
                asteriskStack.push(i);
            } else {
                if (!leftStack.empty()) {
                    leftStack.pop();
                } else if (!asteriskStack.empty()) {
                    asteriskStack.pop();
                } else {
                    return false;
                }
            }
        }

        while (!leftStack.empty() && !asteriskStack.empty()) {
            int leftIndex = leftStack.top();
            leftStack.pop();
            int asteriskIndex = asteriskStack.top();
            asteriskStack.pop();
            if (leftIndex > asteriskIndex) {
                return false;
            }
        }
        
        return leftStack.empty();
    }
};

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/valid-parenthesis-string/solution/you-xiao-de-gua-hao-zi-fu-chuan-by-leetc-osi3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

时间=空间=on

---

法3 贪心
比较黑科技，但是很实用

注意普通的括号匹配中，栈的存在是不必要的，只需要保存左括号的个数
在这个题中，左括号的数量从1个值变成了一个范围，因此，我们用2个值作为这个范围的上下界

如果遇到左括号，则将最小值和最大值分别加 1；

如果遇到右括号，则将最小值和最大值分别减 1；

如果遇到星号，则将最小值减 1，将最大值加 1。

class Solution {
public:
    bool checkValidString(string s) {
        int minCount = 0, maxCount = 0;
        int n = s.size();
        for (int i = 0; i < n; i++) {
            char c = s[i];
            if (c == '(') {
                minCount++;
                maxCount++;
            } else if (c == ')') {
                minCount = max(minCount - 1, 0);
                maxCount--;
                if (maxCount < 0) {
                    return false;
                }
            } else {
                minCount = max(minCount - 1, 0);
                maxCount++;
            }
        }
        return minCount == 0;
    }
};

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/valid-parenthesis-string/solution/you-xiao-de-gua-hao-zi-fu-chuan-by-leetc-osi3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29