Description#
A parentheses string is a non-empty string consisting only of '('
and ')'
. It is valid if any of the following conditions is true:
- It is
()
. - It can be written as
AB
(A
concatenated with B
), where A
and B
are valid parentheses strings. - It can be written as
(A)
, where A
is a valid parentheses string.
You are given a parentheses string s
and a string locked
, both of length n
. locked
is a binary string consisting only of '0'
s and '1'
s. For each index i
of locked
,
- If
locked[i]
is '1'
, you cannot change s[i]
. - But if
locked[i]
is '0'
, you can change s[i]
to either '('
or ')'
.
Return true
if you can make s
a valid parentheses string. Otherwise, return false
.
Example 1:
![](https://spcdn.pages.dev/leetcode/problems/2116.Check%20if%20a%20Parentheses%20String%20Can%20Be%20Valid/images/eg1.png)
Input: s = "))()))", locked = "010100"
Output: true
Explanation: locked[1] == '1' and locked[3] == '1', so we cannot change s[1] or s[3].
We change s[0] and s[4] to '(' while leaving s[2] and s[5] unchanged to make s valid.
Example 2:
Input: s = "()()", locked = "0000"
Output: true
Explanation: We do not need to make any changes because s is already valid.
Example 3:
Input: s = ")", locked = "0"
Output: false
Explanation: locked permits us to change s[0].
Changing s[0] to either '(' or ')' will not make s valid.
Constraints:
n == s.length == locked.length
1 <= n <= 105
s[i]
is either '('
or ')'
.locked[i]
is either '0'
or '1'
.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution:
def canBeValid(self, s: str, locked: str) -> bool:
n = len(s)
if n & 1:
return False
x = 0
for i in range(n):
if s[i] == '(' or locked[i] == '0':
x += 1
elif x:
x -= 1
else:
return False
x = 0
for i in range(n - 1, -1, -1):
if s[i] == ')' or locked[i] == '0':
x += 1
elif x:
x -= 1
else:
return False
return True
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public boolean canBeValid(String s, String locked) {
int n = s.length();
if (n % 2 == 1) {
return false;
}
int x = 0;
for (int i = 0; i < n; ++i) {
if (s.charAt(i) == '(' || locked.charAt(i) == '0') {
++x;
} else if (x > 0) {
--x;
} else {
return false;
}
}
x = 0;
for (int i = n - 1; i >= 0; --i) {
if (s.charAt(i) == ')' || locked.charAt(i) == '0') {
++x;
} else if (x > 0) {
--x;
} else {
return false;
}
}
return true;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public:
bool canBeValid(string s, string locked) {
int n = s.size();
if (n & 1) {
return false;
}
int x = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == '(' || locked[i] == '0') {
++x;
} else if (x) {
--x;
} else {
return false;
}
}
x = 0;
for (int i = n - 1; i >= 0; --i) {
if (s[i] == ')' || locked[i] == '0') {
++x;
} else if (x) {
--x;
} else {
return false;
}
}
return true;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| func canBeValid(s string, locked string) bool {
n := len(s)
if n%2 == 1 {
return false
}
x := 0
for i := range s {
if s[i] == '(' || locked[i] == '0' {
x++
} else if x > 0 {
x--
} else {
return false
}
}
x = 0
for i := n - 1; i >= 0; i-- {
if s[i] == ')' || locked[i] == '0' {
x++
} else if x > 0 {
x--
} else {
return false
}
}
return true
}
|