Leetcode #20 — Valid Parentheses (Python)

Hello everyone, today we’ll be looking at the Valid Parentheses problem. This question is marked as “Easy” on Leetcode.

Problem Statement

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.

Examples from Leetcode

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

Solution

Submission on Leetcode

Explanation (with two examples)

1. Let's call: isValid('()[]{}')
- We create a mapping of the inner parentheses relating to their outer parentheses with -> mapping = {"(": ")", "[": "]",  "{": "}"}
- Create a stack 'stack' which will be used to store the opening parentheses.
- Traverse through each bracket in the input string. 
- Iteration 1: char = '(' ... this satisfies the if condition as char is in '({['. As a result, append '(' to the stack. 'stack' is now ['('].
- Iteration 2: char = ')' ... this doesn't satisfy the if condition, but it does satisfy the elif condition. 'stack' is not empty and char == mapping[stack[-1]] is True because char == mapping['('] => ')' == ')' ... stack.pop() is called, and so 'stack' is now [].
- Iteration 3: char = '[' ... this satisfies the if condition as char is in '({['. As a result, append '[' to the stack. 'stack' is now ['['].
- Iteration 4: char = ']' ... this doesn't satisfy the if condition, but it does satisfy the elif condition. 'stack' is not empty and char == mapping[stack[-1]] is True because char == mapping['['] => ']' == ']' ... stack.pop() is called, and so 'stack' is now [].
- Iteration 5: char = '{' ... this satisfies the if condition as char is in '({['. As a result, append '{' to the stack. 'stack' is now ['{'].
- Iteration 6: char = '}' ... this doesn't satisfy the if condition, but it does satisfy the elif condition. 'stack' is not empty and char == mapping[stack[-1]] is True because char == mapping['{'] => '}' == '}' ... stack.pop() is called, and so 'stack' is now [].
- The for loop is now complete and since the len(stack) == 0 is True, we return True. This means that the input string is valid.

2. Let's call: isValid('([)]')
- We create a mapping of the inner parentheses relating to their outer parentheses with -> mapping = {"(": ")", "[": "]",  "{": "}"}
- Create a stack 'stack' which will be used to store the opening parentheses.
- Traverse through each bracket in the input string.
- Iteration 1: char = '(' ... this satisfies the if condition as char is in '({['. As a result, append '(' to the stack. 'stack' is now ['('].
- Iteration 2: char = '[' ... this satisfies the if condition as char is in '({['. As a result, append '[' to the stack. 'stack' is now ['(', '['].
- Iteration 3: char = ')' ... this doesn't satisfy the if condition, or the elif condition because char == mapping[stack[-1]] is False ... char == mapping['['] => ')' != ']' ... so else will get triggered and False will be returned. 
- This means that the input string is invalid.

Time complexity: O(n)

Space complexity: O(n)

Dhairya Dave