Valid Parentheses

Valid Parentheses#

Twitter Handle LinkedIn Profile GitHub Profile LeetCode Problem Difficulty

from dataclasses import dataclass, field
from typing import Dict

Problem#

Leetcode: Valid Parentheses.

Given a string containing just the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.

An input string is valid if:

  • Open brackets must be closed by the same type of brackets.

  • Open brackets must be closed in the correct order.

  • Every close bracket has a corresponding open bracket of the same type.

Constraints and Assumptions#

We have

  • \(1 \leq \text{s.length} \leq 10^4\)

  • s consists of parentheses only ‘()[]{}’ (i.e. no other characters inside this string, s = “abc()” will not appear).

  • Empty string "" yields True.

Implementation#

Subset of Problem#

We implement a solution that checks for only 1 type of parentheses ().

def is_valid_parentheses(string: str) -> bool:
    """Check if a string is valid for one type of parentheses."""
    stack: StackList[str] = StackList()

    if string[0] == ")":
        return False

    for s in string:
        if s == "(":
            stack.push(s)
        else:  # s == ")"
            if stack.is_empty():
                return False
            stack.pop()

    if stack.is_empty():
        return True
    return False

print(is_valid_parentheses("("))  # expected False
print(is_valid_parentheses("((()))"))  # expected True
print(is_valid_parentheses("((()()))"))  # expected True
print(is_valid_parentheses("(()"))  # expected False
print(is_valid_parentheses(")("))  # expected False
print(is_valid_parentheses("(()))"))  # expected False

False
True
True
False
False
False

The Full Problem#

Leetcode’s solution is quite good, so we will gladly reference to it.

It’s algorithm is as follows:

Algorithm 14 (Valid Parentheses Using Stack)

Inputs: Given a string containing just the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’

Output: Return true if the input string is valid, otherwise return false.

Validity: An input string is valid if:

  • Open brackets must be closed by the same type of brackets.

  • Open brackets must be closed in the correct order.

  • Every close bracket has a corresponding open bracket of the same type.

Algorithm:

  • Initialize an empty stack s.

  • Initialize a mapping that maps the closed bracket to its open counterpart: mapping = {")": "(", "}": "{", "]": "["}

  • Process each bracket of the expression one at a time. This means we loop over the input string.

  • If we encounter an opening bracket, we simply push it onto the stack. This means if the character of the string is not in the keys of mapping, then this character must be an opening bracket. We will keep pushing the open bracket until we encounter the first close bracket.

  • Else, we encounter a closing bracket, then we check the element on top of the stack.

    • If the element at the top of the stack is an opening bracket of the same type, then we pop it off the stack and continue processing.

    • Else, this implies an invalid expression. This is the key, as when you encounter a close bracket, then its immediate predecessor must be its corresponding open bracket (i.e. ([{}]) vs ([)]).

  • In the end, if we are left with a stack still having elements, then this implies an invalid expression, else it is valid.

@dataclass(frozen=False, init=True)
class Solution:
    mapping: Dict[str, str]  # {")": "(", "}": "{", "]": "["}
    # stack: StackList[str] = StackList()  # The stack to keep track of opening brackets.
    stack: StackList[str] = field(default_factory=StackList)

    def is_valid_parentheses(self, string: str) -> bool:
        """Check if a string is valid parentheses."""
        for char in string:
            # if the char is not in mapping means it is an opening bracket
            # so we push it to the stack
            if char not in self.mapping:
                self.stack.push(char)
            else:
                # the else clause means we have a closing bracket,
                # we first check if the stack is empty, if it is we return False.
                # This checks for the case where we start the string with a closing bracket.
                # i.e. ")(){}(" returns False immediately after the first iteration
                # because we have a closing bracket and the stack is empty.
                if self.stack.is_empty():
                    return False
                else:
                    # get the top element of the stack and pop at the same time
                    # this works since stack is not empty
                    top_element = self.stack.pop()

                    # if the top element of the stack (an opening bracket) does not match
                    # the corresponding closing bracket in the mapping, then we return False
                    # for example, if we have "[)" then this check will return False
                    if self.mapping[char] != top_element:
                        return False
                    else:
                        # else the top element of the stack and the current char forms a pair
                        # so we continue to the next char
                        continue

        # In the end, if the stack is empty, then we have a valid expression.
        # The stack won't be empty for cases like ((() so we return False
        if self.stack.is_empty():
            return True
        return False

Mutation!

I appreciate why dataclasses forces you to use field(default) when defining a mutable container such as list.

I have no idea why my code kept overwriting and soon I figured that my StackList object is a mutable container, and this is why you cannot just instantiate an empty list in dataclasses by

mylist: List = []

so in here it should be

stack: StackList[str] = field(default_factory=StackList)

as well instead.

mapping = {")": "(", "}": "{", "]": "["}

print(Solution(mapping).is_valid_parentheses("{({([][])}())}")) # True
print(Solution(mapping).is_valid_parentheses("}{")) # False
print(Solution(mapping).is_valid_parentheses("{({([][])}())}}")) # False
print(Solution(mapping).is_valid_parentheses("{{({([][])}())}")) # False
print(Solution(mapping).is_valid_parentheses("")) # False

True
False
False
False
True

My implementation as a first run is very unclean, with unnecessary returns in if-else blocks.

This helps me to visualize easier and will refactor it in future.

Time Complexity#

Assume the string has length \(n\).

From Stack List Time Complexity, operations such as push, pop, is_empty() and != here are all \(\O(1)\).

And since we traverse the given string one character at a time for at most \(n\) times, then the time complexity is \(\O(1) \times n \approx \O(n)\).

Space Complexity#

Assume the string has length \(n\).

The space complexity is at most \(\O(n)\) as we are just maintaining a stack with at most \(n\) elements pushed in.

Further Readings#