Today’s problem

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

Intuition

To make a parentheses string, we need to find a ‘(’ for every ‘)’ on its left side, and a ‘)’ for every ‘(’ on its right hand side. We can fulfill the first requirement first as we are iterating from left to right.

When we encounter a ‘)’, there are three ways to find him a ‘(’, one is a ‘(’ that is already existing, another is to find him a ‘)’ that is unlocked, and the last way is to turn him into a ‘(’ if it is unlocked itself.

Now, assume that we have find all ‘)’ a ‘(’, then we now need to find all ‘(’ a ‘)’. Now, the only way to find a ‘(’ on its right side is to find a ‘(’ that is unlocked, because all ‘)’ is matched with a ‘(’.

Approach

First of all, not that is the length is odd, then it could never be a parentheses string, so please just return False.

We can store two arrays, one $anyBracket$ that stores the index all unlocked brackets, and another $openBracket$ stroing all ‘(’.

Now we iterate the whole string from left to right, here are some situations we would meet:

  1. This is a unlocked bracket: Then we could put it into our $anyBracket$ stack.
  2. This is a ‘(’: Then we could put it into our $openBracket$ stack.
  3. This is a ‘)’: Then we need to find him a ‘(’.
    • First we would like to find him a ‘(’ in our $openBracket$ stack, which will also finish the task that helps a ‘(’ to find a ‘)’.
    • Then if our $openBracket$ stack is empty, then we will find him a ‘(’ in our $anyBracket$ stack by either a ‘(’ or a ‘)’ that is unlocked.
    • If both our $openBracket$ stack and our $anyBracket$ stack are empty, then return False, because we cannot find a ‘(’ for him.

Now we might left some ‘(’ that is unmatched.

Then we can iterate every ‘(’ in our $openBracket$ stack to find whether there is a ‘(’ or ‘)’ in our $anyBracket$ stack that has a larger index than our current ‘(’.

  • If there is, then we successfully find him a ‘)’, congratulations!
  • Otherwise we cannot find him a ‘)’, which leads to return False

Now if there are even number in our $anyBracket$ stack (which will always be the case because we have already did the singularity test above), please return True, then you are all set!

Important Trick

  • Why we need a stack for $openBracket$ and $anyBracket$?
  • Because in this situation, a ‘)’ will always match to the nearest ‘(’ on its left hand site, which means we need a FIFO (First in First out) data structure to get “the nearest object”.

Complexity

  • Time complexity: $O(N)$, N is the length of the string.

  • Space complexity: $O(N)$, we stored the indexs of the brackets.

Code

class Solution:
    def canBeValid(self, s: str, locked: str) -> bool:
        if len(s) % 2 == 1:
            return False
        
        openBracket = []
        anyBracket = []

        for i in range(len(s)):
            if locked[i] == '0':
                anyBracket.append(i)
            else:
                if s[i] == '(':
                    openBracket.append(i)
                else:
                    if len(openBracket) > 0:
                        openBracket.pop()
                    elif len(anyBracket) > 0:
                        anyBracket.pop()
                    else:
                        return False
        
        if len(anyBracket) < len(openBracket):
            return False

        idx = len(anyBracket) - 1
        for i in range(len(openBracket) - 1, -1, -1):
            if anyBracket[idx] < openBracket[i]:
                return False
            idx -= 1
        
        return idx % 2 == 1

image.png