Check if a Parentheses String Can Be Valid
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(Aconcatenated withB), whereAandBare valid parentheses strings. - It can be written as
(A), whereAis 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 changes[i]. - If
locked[i]is'0', you can changes[i]to either'('or')'.
Return true if you can make s a valid parentheses string. Otherwise, return false.
Example 1
Input
s = "))()))", locked = "010100"Output
truelocked[1] == '1' and locked[3] == '1', so s[1] and s[3] cannot be changed; changing s[0] and s[4] to '(' makes s valid.Example 2
Input
s = "()()", locked = "0000"Output
trues is already valid, so no changes are needed.Constraints
- n == s.length == locked.length
- 1 <= n <= 10^5
- s[i] is either '(' or ')'.
- locked[i] is either '0' or '1'.