2116. Check if a Parentheses String Can Be Valid

Problem

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.

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

Example 1:

case1

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 <= 10⁵
s[i] is either '(' or ')'.
locked[i] is either '0' or '1'.

Test Cases

1 2	class Solution: def canBeValid(self, s: str, locked: str) -> bool:

solution_test.py

import pytest

from solution import Solution


@pytest.mark.parametrize('s, locked, expected', [
    ("))()))", "010100", True),
    ("()()", "0000", True),
    (")", "0", False),

    ("())()))()(()(((())(()()))))((((()())(())", "1011101100010001001011000000110010100101", True),
    ("()))(()(()()()()(((())())((()((())", "1100000000000010000100001000001101", True),
    (
        "(()))()))(()((()()(((()))()()()()()())))()()(()())()(()((()()((()((((((()(()()(()()())(((((())((()))))()(((((((()()())()))())((((((()(())())()((())()()((())((((())(((())(())()()))(((()()())())))((()))))()()()((()))())(())(((()()((())(())(())())()((()))())(())()(()())((((()(((())((()()())(((()(((((()))()))))))(()((())())(())))))(())(((())()()(()))())())))(((())))()()))()())))))())()(()()))(())(()())))())()))((((())(()))()(((())())(()(()))()))((()(())()()))))())(()(((((()",
        "110001111001011100000100011110101000100110010010011001110010111111100111000100000000101111101001111111011101001110011001001100100001100000000010100010101101100000100001000110111000111110110010111011010010100011111101110011100010010001111001010001001000111101101111111011001000100111100110101000100011011001001100110011111111111100101000100111111100000100101101000101111101000011110001001011111010011010000100100000000011101011001110000110011000100001110101100101111111110100",
        False,
    ),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, s, locked, expected):
    assert sol.canBeValid(s, locked) == expected

Thoughts

如果 n 是奇数则肯定不行。

从左向右遍历，看锁定的右括号是不是都能配对。如果一个位置是未锁定的，则可以放左括号也可以放右括号，记住有多少个。如果是锁定的左括号，计数加一。如果是锁定的右括号，则先消耗一个已知的锁定的左括号，如果没有则消耗一个未锁定的位置，如果也没有则无法完成配对。

同理从右向左遍历，看锁定的左括号是不是都能配对。

时间复杂度 O(n)，空间复杂度 O(1)。

Code

solution.py

class Solution:
    def canBeValid(self, s: str, locked: str) -> bool:
        n = len(s)
        if n & 1 or locked[0] == '1' and s[0] == ')' or locked[-1] == '1' and s[-1] == '(':
            return False

        open = 0
        empty = 0
        for i in range(n):
            if locked[i] == '0':
                empty += 1
            elif s[i] == '(':
                open += 1
            elif open:
                open -= 1
            elif empty:
                empty -= 1
            else:
                return False

        close = 0
        empty = 0
        for i in range(n - 1, -1, -1):
            if locked[i] == '0':
                empty += 1
            elif s[i] == ')':
                close += 1
            elif close:
                close -= 1
            elif empty:
                empty -= 1
            else:
                return False

        return True

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。