Valid Parentheses

Patrick Leaton
Published: Feb. 22, 2021, 6:28 p.m.
Problem Description

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

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

Example 4:

Input: s = "([)]"
Output: false

Example 5:

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

Constraints:

  • 1 <= s.length <= 104
  • s consists of parentheses only '()[]{}'.

 

The description was taken from https://leetcode.com/problems/valid-parentheses/.

Problem Solution

#O(N) Time, O(N) Space
class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        pairs = {"]":"[", "}":"{", ")":"("}
        for bracket in s:
            if bracket in pairs.values():
                stack.append(bracket)
            elif bracket in pairs.keys():
                if stack == []:
                    return False
                elif pairs[bracket] != stack.pop():
                    return False
            else:
                return False
        return stack == []

Problem Explanation

This problem relies heavily on matching pairs.  When traversing the string, the order of the opening brackets does not matter until you get to a closing bracket.  Once that happens, we would need to know which opening bracket we just saw.  

Here, we can utilize a stack since it utilizes a last-in, first-out principle.  The last thing we put in we can immediately retrieve, so the last opening bracket we put in we can immediately retrieve and verify it is a matching pair with the closing bracket we just encountered.  We will repeat this until we have traversed the entire string.

The two rules that we need to validate to ensure a string is valid are:

  1. Closing brackets cannot come before opening brackets.
  2. Opening brackets must be closed with brackets of the same type.

With most string validation problems, we will write conditional statements to try and falsify the string.  If at the end of the traversal we didn't return the string as invalid, we will have a valid string.

 We can use a stack and a HashMap to solve this problem.

        stack = []
        pairs = {"]":"[", "}":"{", ")":"("}

 

We will iterate through the brackets string and check whether the bracket is an opening or closing bracket.   If it is an opening bracket, we will push it onto the stack. 

        for bracket in s:
            if bracket in pairs.values():
                stack.append(bracket)

 

 If it is a closing bracket, we first want to make sure the stack isn’t empty.  If it is, then the parentheses are invalid due to the first rule.

            elif bracket in pairs.keys():
                if stack == []:
                    return False

 

If it is not empty, then we will pop the stack to see if the closing bracket matches the corresponding opening bracket within our dictionary and return false if it isn't, due to the second rule.

                elif pairs[bracket] != stack.pop():
                    return False

 

If the bracket we’re looking at isn’t in the dictionary keys or values, then it isn’t actually a bracket so we will return false.

            else:
                return False

 

At the end of the function, we should have an empty stack, so we will return whether this is true or not.

        return stack == []

We'll need to traverse the entire string to get our solution so this will require linear time.  In the worst case, we'll push all the brackets onto our stack so this will require linear space.