-
题目链接:678. 有效的括号字符串
-
我的题解:
class Solution { public: bool checkValidString(string s) { vector<int> tmp; int start = 0; for (char ch: s) { if (ch == '(' || ch == '*') { if (ch=='*'){ start++; } tmp.push_back(ch); } else { if (tmp.empty()) { return false; } bool seenleft = false; for (int i = tmp.size() - 1; i >= 0; --i) { if (tmp[i] == '(') { seenleft = true; tmp.erase(tmp.begin() + i); break; } } if (seenleft == false) { tmp.pop_back(); start--; } } } int start1 = 0; for (int i = tmp.size() - 1; i >= 0; --i) { if (tmp[i] == '(') { start1--; if (start1 < 0) { return false; } } if (tmp[i] == '*') { start1++; } } return true; } };
-
复杂度: