Valid Parentheses

Problem Statement

You are given a string s consisting of the following characters: \'(\', \')\', \'{\', \'}\', \'[\' and \']\'.

The input string s is valid if and only if:

1. Every open bracket is closed by the same type of close bracket.
2. Open brackets are closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

Return true if s is a valid string, and false otherwise.

Example 1:

Input: s = "[]"

Output: true

Example 2:

Input: s = "([{}])"

Output: true

Example 3:

Input: s = "[(])"

Output: false

Explanation: The brackets are not closed in the correct order.

Constraints:

• 1 <= s.length <= 1000

You should aim for a solution with O(n) time and O(n) space, where n is the length of the given string.

Recommended Time and Space Complexity

You should aim for a solution with O(n) time and O(n) space, where n is the length of the given string.

Hint 1

A brute force solution would be to continuously remove valid brackets until no more can be removed. If the remaining string is empty, return true; otherwise, return false. This would result in an O(n^2) solution. Can we think of a better approach? Perhaps a data structure could help.

Hint 2

We can use a stack to store characters. Iterate through the string by index. For an opening bracket, push it onto the stack. If the bracket is a closing type, check for the corresponding opening bracket at the top of the stack. If we don’t find the corresponding opening bracket, immediately return false. Why does this work?

Hint 3

In a valid parenthesis expression, every opening bracket must have a corresponding closing bracket. The stack is used to process the valid string, and it should be empty after the entire process. This ensures that there is a valid substring between each opening and closing bracket.

Solution

Brute Force

def is_valid(s: str) -> bool:
    """
    Checks if the input string s is a valid string using brute force approach.
    """
    while '()' in s or '{}' in s or '[]' in s:
        s = s.replace('()', '')
        s = s.replace('{}', '')
        s = s.replace('[]', '')
    return s == ''

Time complexity: O(n^2) Space complexity: O(n)

Stack

def is_valid(s: str) -> bool:
    """
    Checks if the input string s is a valid string using stack approach.
    """
    stack = []
    close_to_open = {")": "(", "]": "[", "}": "{"}

    for char in s:
        if char in close_to_open:
            if stack and stack[-1] == close_to_open[char]:
                stack.pop()
            else:
                return False
        else:
            stack.append(char)

    return not stack

Time complexity: O(n) Space complexity: O(n)