力扣2116.判断一个括号字符串是否有效
-
双栈模拟
- 一个锁栈，一个非锁栈
- 遇到锁)时，优先匹配锁栈的(
-
class Solution {public:bool canBeValid(string s, string locked) {if(s.size() % 2 != 0) return false;stack<int> free_stk;stack<int> lock_stk;for(int i=0;i<s.size();i++){if(locked[i] != '1')free_stk.push(i);else{if(s[i] == ')'){//优先匹配锁栈if(!lock_stk.empty()) lock_stk.pop();else if(!free_stk.empty()) free_stk.pop();else return false;}elselock_stk.push(i);}}//最后处理所有锁的(//处理完剩下的非锁栈元素一定可以自己匹配完while(!free_stk.empty() && !lock_stk.empty()){if(free_stk.top() < lock_stk.top()) return false;free_stk.pop(),lock_stk.pop();}return lock_stk.empty();}};
