Valid parentheses#

Levels: level-1

Data structures: string, stack

Practice Link#

LeetCode

Description#

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.

Note:

An empty string is also considered valid.

Examples#

1Input: "()[]{}"
2Output: true

1# Input: "([)]"
2# Output: false

Python Solution#

 1class Solution(object):
 2    def isValid(self, s):
 3        """
 4        :type s: str
 5        :rtype: bool
 6        """
 7
 8        # The stack to keep track of opening brackets.
 9        stack = []
10
11        # Hash map for keeping track of mappings. This keeps the code very clean.
12        # Also makes adding more types of parenthesis easier
13        mapping = {")": "(", "}": "{", "]": "["}
14
15        # For every bracket in the expression.
16        for char in s:
17
18            # If the character is an closing bracket
19            if char in mapping:
20
21                # Pop the topmost element from the stack, if it is non empty
22                # Otherwise assign a dummy value of '#' to the top_element variable
23                top_element = stack.pop() if stack else '#'
24
25                # The mapping for the opening bracket in our hash and the top
26                # element of the stack don't match, return False
27                if mapping[char] != top_element:
28                    return False
29            else:
30                # We have an opening bracket, simply push it onto the stack.
31                stack.append(char)
32
33        # In the end, if the stack is empty, then we have a valid expression.
34        # The stack won't be empty for cases like ((()
35        return not stack