LeetCode 2116.判断一个括号字符串是否有效：括号匹配(两个变量一次遍历办 ...

【LetMeFly】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 是 '1' ，你 不能 改变 s 。
  
• 如果 locked 是 '0' ，你 可以 将 s 变为 '(' 大概 ')' 。
  

如果你可以将 s 变为有效括号字符串，请你返回 true ，否则返回 false 。
 
示例 1：

1. <b>输入：</b>s = "))()))", locked = "010100"
2. <b>输出：</b>true
3. <b>解释：</b>locked[1] == '1' 和 locked[3] == '1' ，所以我们无法改变 s[1] 或者 s[3] 。
4. 我们可以将 s[0] 和 s[4] 变为 '(' ，不改变 s[2] 和 s[5] ，使 s 变为有效字符串。

复制代码

示例 2：

1. <b>输入：</b>s = "()()", locked = "0000"
2. <b>输出：</b>true
3. <b>解释：</b>我们不需要做任何改变，因为 s 已经是有效字符串了。

复制代码

示例 3：

1. <b>输入：</b>s = ")", locked = "0"
2. <b>输出：</b>false
3. <b>解释：</b>locked 允许改变 s[0] 。
4. 但无论将 s[0] 变为 '(' 或者 ')' 都无法使 s 变为有效字符串。

复制代码

 
提示：

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

很不错的一道题，这题灵茶山艾府的题解很棒。
解题方法：一次遍历

解题思路

整个遍历过程中，要时刻保证：

• 左括号的数量始终不少于右括号的数量
  

遍历竣事后，要保证左括号的数量和右括号的数量相等。
我们可以利用                                   d                         i                         f                         f                              diff                  diff来表示左括号的数量减去右括号的数量的差值，则想要返回true必须满足：

• 遍历过程中始终有：                                        d                            i                            f                            f                            ≥                            0                                  diff\geq 0                     diff≥0
  
• 遍历竣事时，                                        d                            i                            f                            f                            =                            0                                  diff = 0                     diff=0
  

如果每个字符都是确定的话还好说，但是有的字符可以更改（locked = '0'）要怎么处置惩罚呢？
其实也很简单，是(是)都试试呗。不难发现：
   假设                                        d                            i                            f                            f                            =                            3                                  diff=3                     diff=3时遇到了一个locked = '0'，那么s为(的话                                        d                            i                            f                            f                                  diff                     diff将变成                                        4                                  4                     4，s为)的话                                        d                            i                            f                            f                                  diff                     diff将变成                                        6                                  6                     6。                                        d                            i                            f                            f                                  diff                     diff的取值范围变成了                                        {                            4                            ,                            6                            }                                  \{4, 6\}                     {4,6}（全为偶数）
  在此基础上，假设又遇到了locked = '0'，那么s为(的话                                        d                            i                            f                            f                                  diff                     diff将变成                                        {                            3                            ,                            5                            }                                  \{3, 5\}                     {3,5}，s为)的话                                        d                            i                            f                            f                                  diff                     diff将变成                                        {                            5                            ,                            7                            }                                  \{5, 7\}                     {5,7}。                                        d                            i                            f                            f                                  diff                     diff的取值范围变成了                                        {                            3                            ,                            5                            ,                            7                            }                                  \{3, 5, 7\}                     {3,5,7}（满是奇数）
  不难发现                                        d                            i                            f                            f                                  diff                     diff的取值范围要么是全奇数，要么是全偶数。所以可以用                                        l                                  l                     l表示                                        d                            i                            f                            f                                  diff                     diff合法取值范围的最小值，                                        r                                  r                     r表示                                        d                            i                            f                            f                                  diff                     diff合法取值范围的最大值。
  具体做法

初始值                                   l                         =                         0                         ,                         r                         =                         0                              l = 0, r = 0                  l=0,r=0，代表(和)差值的可能范围为                                   {                         0                         }                              \{0\}                  {0}。
开始遍历字符串：

• 如果locked = '0'，说明可(可)，范围将变成l - 1到r + 1
  注意如果l变成了-1则说明l本来是0，要将l重新置为合法范围1
  
• 否则（locked = '1'）
  
  
  
  • 如果s = '('：范围将变成l + 1到r + 1
    
  • 否则(s = ')')：范围将变成l - 1到r - 1
    此时如果r < 0，则说明合法范围为空，不满足“整个遍历过从始终有                                                       d                                     i                                     f                                     f                                     ≥                                     0                                              diff\geq 0                              diff≥0”，直接返回false
    此时如果l < 0（l变成了-1），则说明l本来是0，要将l重新置为合法范围1
    
  
  

终极，若l为0则说存在(和)相等的环境，返回true。
时空复杂度

• 时间复杂度                                        O                            (                            l                            e                            n                            (                            s                            )                            )                                  O(len(s))                     O(len(s))
  
• 空间复杂度                                        O                            (                            1                            )                                  O(1)                     O(1)
  

AC代码

C++

1. /*
2. * @Author: LetMeFly
3. * @Date: 2025-03-23 09:37:28
4. * @LastEditors: LetMeFly.xyz
5. * @LastEditTime: 2025-03-23 10:39:28
6. */
7. #ifdef _WIN32
8. #include "_[1,2]toVector.h"
9. #endif
11. /*
12. *)*(**
13. ()(())
16. (*)*
17. (())
20. (**(
21. xxxx
23. (*
24. ()
28. */
29. class Solution {
30. public:
31.     bool canBeValid(string s, string locked) {
32.         int l = 0, r = 0;
33.         for (int i = 0; i < s.size(); i++) {
34.             if (locked[i] == '0') {
35.                 l--, r++;
36.                 if (l < 0) {
37.                     l = 1;
38.                 }
39.             } else {  // ()
40.                 if (s[i] == '(') {
41.                     l++, r++;
42.                 } else {
43.                     l--, r--;
44.                     if (r < 0) {
45.                         return false;
46.                     }
47.                     if (l < 0) {
48.                         l = 1;
49.                     }
50.                 }
51.             }
52.         }
53.         return !l;
54.     }
55. };

复制代码

Python

1. '''
2. Author: LetMeFly
3. Date: 2025-03-23 10:49:44
4. LastEditors: LetMeFly.xyz
5. LastEditTime: 2025-03-23 10:51:19
6. '''
7. class Solution:
8.     def canBeValid(self, s: str, locked: str) -> bool:
9.         l = r = 0
10.         for i in range(len(s)):
11.             if locked[i] == '0':
12.                 l -= 1
13.                 r += 1
14.                 if l == -1:
15.                     l = 1
16.             else:
17.                 if s[i] == '(':
18.                     l += 1
19.                     r += 1
20.                 else:
21.                     l -= 1
22.                     r -= 1
23.                     if r < 0:
24.                         return False
25.                     if l < 0:
26.                         l = 1
27.         return not l

复制代码

Java

1. /*
2. * @Author: LetMeFly
3. * @Date: 2025-03-23 10:52:22
4. * @LastEditors: LetMeFly.xyz
5. * @LastEditTime: 2025-03-23 10:53:49
6. */
7. class Solution {
8.     public boolean canBeValid(String s, String locked) {
9.         int l = 0, r = 0;
10.         for (int i = 0; i < s.length(); i++) {
11.             if (locked.charAt(i) == '0') {
12.                 l--;
13.                 r++;
14.                 if (l < 0) {
15.                     l = 1;
16.                 }
17.             } else {
18.                 if (s.charAt(i) == '(') {
19.                     l++;
20.                     r++;
21.                 } else {
22.                     l--;
23.                     r--;
24.                     if (r < 0) {
25.                         return false;
26.                     }
27.                     if (l < 0) {
28.                         l = 1;
29.                     }
30.                 }
31.             }
32.         }
33.         return l == 0;
34.     }
35. }

复制代码

Go

1. /*
2. * @Author: LetMeFly
3. * @Date: 2025-03-23 10:54:53
4. * @LastEditors: LetMeFly.xyz
5. * @LastEditTime: 2025-03-23 10:56:04
6. */
7. package main
9. func canBeValid(s string, locked string) bool {
10.     l, r := 0, 0
11.     for i := range s {
12.         if locked[i] == '0' {
13.             l--
14.             r++
15.             if l < 0 {
16.                 l = 1
17.             }
18.         } else {
19.             if s[i] == '(' {
20.                 l++
21.                 r++
22.             } else {
23.                 l--
24.                 r--
25.                 if r < 0 {
26.                     return false
27.                 }
28.                 if l < 0 {
29.                     l = 1
30.                 }
31.             }
32.         }
33.     }
34.     return l == 0
35. }

复制代码

  同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
  千篇源码题解已开源

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