有效的括号字符串 123456789101112131415161718192021class 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; }}; 12345678910111213141516171819202122class 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]; }};