LeetCode 2116. 判斷一個括号字元串是否有效（棧）

文章目錄

• 1. 題目
• 2. 解題

1. 題目

一個括号字元串是隻由

'(' 和 ')'

組成的 非空 字元串。

如果一個字元串滿足下面 任意 一個條件，那麼它就是有效的：

• 字元串為

  ()

  .
• 它可以表示為

  AB

  （A 與 B 連接配接），其中A 和 B 都是有效括号字元串。
• 它可以表示為

  (A)

  ，其中 A 是一個有效括号字元串。

給你一個括号字元串 s 和一個字元串 locked ，兩者長度都為 n 。

locked 是一個二進制字元串，隻包含 ‘0’ 和 ‘1’ 。對于 locked 中 每一個 下标 i ：

• 如果

  locked[i] 是 '1'

  ，你 不能 改變

  s[i]

  。
• 如果

  locked[i] 是 '0'

  ，你 可以 将 s[i] 變為

  '('

  或者

  ')'

  。

如果你可以将 s 變為有效括号字元串，請你傳回 true ，否則傳回 false 。

示例 1：

輸入：s = "))()))", locked = "010100"
輸出：true
解釋：locked[1] == '1' 和 locked[3] == '1' ，
	是以我們無法改變 s[1] 或者 s[3] 。
我們可以将 s[0] 和 s[4] 變為 '(' ，不改變 s[2] 和 s[5] ，
	使 s 變為有效字元串。

示例 2：
輸入：s = "()()", locked = "0000"
輸出：true
解釋：我們不需要做任何改變，因為 s 已經是有效字元串了。

示例 3：
輸入：s = ")", locked = "0"
輸出：false
解釋：locked 允許改變 s[0] 。
但無論将 s[0] 變為 '(' 或者 ')' 都無法使 s 變為有效字元串。
 
提示：
n == s.length == locked.length
1 <= n <= 10^5
s[i] 要麼是 '(' 要麼是 ')' 。
locked[i] 要麼是 '0' 要麼是 '1' 。           

複制

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/check-if-a-parentheses-string-can-be-valid

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

跟 678 題一樣的

class Solution {
public:
    bool canBeValid(string s, string locked) {
        int n = s.size();
        if(n%2==1) return false;
        stack<int> l;
        stack<int> star;
        for(int i = 0; i < s.size(); ++i)
        {
        	if(s[i] == '(' && locked[i] == '1')
        		l.push(i);
        	else if(locked[i] == '0')
        		star.push(i);
        	else
        	{
        		if(l.empty() && star.empty())
        			return false;//不夠比對
        		if(!l.empty())
        			l.pop();
        		else
        			star.pop();
        	}
        }

        while(!l.empty() && !star.empty())
        {
        	if(l.top() > star.top())// * ( 不能比對
        		return false;
        	l.pop();
        	star.pop();
        }
        return l.empty();
    }
};           

複制

80 ms 30.8 MB C++

我的CSDN部落格位址 https://michael.blog.csdn.net/