Leetcode 20: Valid Parentheses

Problem Statement

Given a string s 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.

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

Solution

Intuition & Patterns

Leetcode #20, Valid Parentheses, is a great introduction to LIFO (last in first out) stack problems. The stack data structure can be visualized as a stack of plates at a buffet. The last plate added to the stack will be the first plate removed by a hungry patron.

In Python, a list or a double ended queue deque from the collections library will function as a stack. We’ll use deque for this problem. Adding and removing items to stack can be performed in O(1) time.

Let’s say we have the following example string "{([{}](){})}". We can see that there is inherent symmetry to the problem that reminds us of the parentheses theorem from the DFS (Depth first search) algorithm. In a strange sort of way, this problem serves as an illustration of an iterative implementation of a recursive algorithm. As we loop through each character of the string, an opening (, [, or { represents calling a recursive functions, whereas each closing ), }, or ] represents returning from a recursive function.

{
    (
        [
            {}
            ]
        ()
        {}
    )
}

Building on these observations, we can develop a simple algorithm. For each closing character, check if the top of the stack is the matching opening element. If it is, we pop it from the stack, if not, we add the current character to the stack. Once we loop over the entire string, the stack will be empty if it conformed to the parenthesis theorem, otherwise it will still have element(s) in it.

We can use a hash table to map closing characters to open characters. If we find a match, we pop() from the stack, otherwise we append(...) to it.

Python Code

from collections import deque
class Solution:
    def isValid(self, s: str) -> bool:
        stack = deque()
        mp = {
            ")": "(",
            "]": "[",
            "}": "{"
        }

        for ch in s:
            if stack and stack[-1] == mp.get(ch):
                stack.pop()
            else:
                stack.append(ch)
        
        return False if stack else True

Leetcode 20 Valid Parentheses