判断合法括号序列问题
题库关键词:括号序列
$O(n)$
左括号进栈 优化空间复杂度-> 遍历字符,记录左括号数量,若遍历过程中出现负数则为false
星号处理:用 low 和 high 记录左括号的数量范围,若出现 low > high 则为false
边界条件:low 最小值为0
class Solution {
public:
bool checkValidString(string s) {
int low = 0, high = 0;
for(auto c: s) {
if(c == '(') low++, high++;
else if(c == ')') low--, high--;
else low--, high++;
low = max(0, low);
if(low > high) return false;
}
return low == 0;
}
};