有效的括号字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  bool checkValidString(string s) {
    int l = 0, r = 0;
    for (auto c : s) {
      if (c == '(') {
        l++;
        r++;
      } else if (c == ')') {
        l--;
        r--;
      } else {
        l--;
        r++;
      }
      l = max(l, 0);
      if (l > r) return false;
    }
    return l == 0;
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  bool checkValidString(string s) {
    int n = s.size();
    vector<vector<bool>> f(n + 1, vector<bool>(n + 1));
    f[0][0] = true;
    for (int i = 1; i <= n; i++) {
      for (int j = 0; j <= i; j++) {
        if (s[i - 1] == '(') {
          if (j - 1 >= 0) f[i][j] = f[i - 1][j - 1];
        } else if (s[i - 1] == ')') {
          if (j + 1 <= i) f[i][j] = f[i - 1][j + 1];
        } else if (s[i - 1] == '*') {
          f[i][j] = f[i - 1][j];
          if (j - 1 >= 0) f[i][j] = f[i][j] | f[i - 1][j - 1];
          if (j + 1 <= i) f[i][j] = f[i][j] | f[i - 1][j + 1];
        }
      }
    }
    return f[n][0];
  }
};