目錄

系列文章目錄

專題總結：

C++刷題技巧總結：

題目?2116. 判斷一個括號字符串是否有效

難度

描述

解題方法1

---

系列文章目錄

專題總結：

1. 【拒絕算法PUA】0x00-位運算
2. 【拒絕算法PUA】0x01- 區間比較技巧
3. 【拒絕算法PUA】0x02- 區間合并技巧
4. 【拒絕算法PUA】0x03 - LeetCode 排序類型刷題
5. 【拒絕算法PUA】LeetCode每日一題系列刷題匯總-2025年持續刷新中

C++刷題技巧總結：

1. 溫習C/C++]0x04 刷題基礎編碼技巧

---

題目?2116. 判斷一個括號字符串是否有效

2116. 判斷一個括號字符串是否有效https://leetcode.cn/problems/check-if-a-parentheses-string-can-be-valid

難度

中等

描述

一個括號字符串是只由?'('?和?')'?組成的?非空?字符串。如果一個字符串滿足下面?任意?一個條件，那么它就是有效的：

• 字符串為?().
• 它可以表示為?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 變為有效字符串。

示例 4：

輸入：s = "(((())(((())", locked = "111111010111"
輸出：true
解釋：locked 允許我們改變 s[6] 和 s[8]。
我們將 s[6] 和 s[8] 改為 ')' 使 s 變為有效字符串。

提示：

• n == s.length == locked.length
• 1 <= n <= 105
• s[i]?要么是?'('?要么是?')'?。
• locked[i]?要么是?'0'?要么是?'1'?。

解題方法1

貪心 + 兩次遍歷

我們觀察發現，奇數長度的字符串一定不是有效的括號字符串，因為無論怎么匹配，都會剩下一個括號。因此，如果字符串?s?的長度是奇數，提前返回?false。

接下來，我們進行兩次遍歷。

第一次從左到右，判斷所有的?'('?括號是否可以被?')'?或者可變括號匹配，如果不可以，直接返回?false。

第二次從右到左，判斷所有的?')'?括號是否可以被?'('?或者可變括號匹配，如果不可以，直接返回?false。

遍歷結束，說明所有的括號都可以被匹配，字符串?s?是有效的括號字符串，返回?true。

class Solution {
public:bool canBeValid(string s, string locked) {int n = s.size();int mx = 0;   // 可以達到的最大分數int mn = 0;   // 可以達到的最小分數 與 最小有效前綴對應分數 的較大值for (int i = 0; i < n; ++i) {if (locked[i] == '1') {// 此時對應字符無法更改int diff;if (s[i] == '(') {diff = 1;}else {diff = -1;}mx += diff;mn = max(mn + diff, (i + 1) % 2);}else {// 此時對應字符可以更改++mx;mn = max(mn - 1, (i + 1) % 2);}if (mx < mn) {// 此時該前綴無法變為有效前綴return false;}}// 最終確定 s 能否通過變換使得分數為 0（成為有效字符串）return mn == 0;}
};

輸出：

test

? 關注我，跟我一起每日一題！
【拒絕算法PUA】LeetCode每日一題系列刷題匯總-2025年持續刷新中