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

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

• 双栈模拟
  
  
  
  • 一个锁栈，一个非锁栈
    
  • 碰到锁)时，优先匹配锁栈的(
    
  
  
• 1.   class Solution {
  2.   public:
  3.       bool canBeValid(string s, string locked) {
  4.           if(s.size() % 2 != 0) return false;
  5.           stack<int> free_stk;
  6.           stack<int> lock_stk;
  7.           for(int i=0;i<s.size();i++)
  8.           {
  9.               if(locked[i] != '1')
  10.                   free_stk.push(i);
  11.               else
  12.               {
  13.                   if(s[i] == ')')
  14.                   {
  15.                       //优先匹配锁栈
  16.                       if(!lock_stk.empty()) lock_stk.pop();
  17.                       else if(!free_stk.empty()) free_stk.pop();
  18.                       else return false;
  19.                   }
  20.                   else
  21.                       lock_stk.push(i);
  22.               }
  23.           }
  24.           //最后处理所有锁的(
  25.           //处理完剩下的非锁栈元素一定可以自己匹配完
  26.           while(!free_stk.empty() && !lock_stk.empty())
  27.           {
  28.               if(free_stk.top() < lock_stk.top()) return false;
  29.               free_stk.pop(),lock_stk.pop();
  30.           }
  31.           return lock_stk.empty();
  32.       }
  33.   };

  复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。