当前位置：首页 > article >正文

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

article 2024/9/21 8:39:33

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