力扣2116.判断一个括号字符串是否有效

力扣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;
                    }
                    else
                        lock_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();
        }
    };