Leetcode 20 - Valid Parentheses
Explanation for Leetcode 20 - Valid Parentheses problem, and its solution in Python.
Problem
Leetcode 20 - Valid Parentheses
Example:
1
2
3
4
5
6
7
8
Input: s = "()"
Output: true
Input: s = "()[]{}"
Output: true
Input: s = "(]"
Output: false
Approach
We can use a stack to keep track of the opening brackets as stack is LIFO meaning the last element added will be the first one to be removed. We can use a hash map to store the pairs of brackets.
As we iterate through the string there are two cases:
- The character is an opening bracket, we can simply push it onto the stack.
- The character is a closing bracket:
- If the stack is not empty and the top of the stack is the matching opening bracket, we pop it from the stack.
- Otherwise, we return false.
After iterating through the string, we need to check if the stack is empty. If it is, that means all the brackets were matched and we return true. Otherwise, we return false as there are unmatched brackets.
Visual representation of the approach:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
s = "([{}])"
stack = []
bracket = { ')': '(', ']': '[', '}': '{' } this is for keeping track of the pairs of brackets
ch = '('
since '(' is an opening bracket, we can simply push it onto the stack
stack = ['(']
ch = '['
since '[' is an opening bracket, we can simply push it onto the stack
stack = ['(', '[']
ch = '{'
since '{' is an opening bracket, we can simply push it onto the stack
stack = ['(', '[', '{']
ch = '}'
since '}' is a closing bracket, we check if the stack is not empty and the top of the stack is the matching opening bracket and since it is, we pop it from the stack
stack = ['(', '[']
ch = ']'
since ']' is a closing bracket, we check if the stack is not empty and the top of the stack is the matching opening bracket and since it is, we pop it from the stack
stack = ['(']
ch = ')'
since ')' is a closing bracket, we check if the stack is not empty and the top of the stack is the matching opening bracket and since it is, we pop it from the stack
stack = []
since the stack is empty, we return true
Here is the implementation of the approach:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def isValid(self, s: str) -> bool:
# initializing stack and bracket hash map
stack = []
bracket = { ')': '(', ']': '[', '}': '{' }
# iterating through the string
for ch in s:
# case 1: the character is a closing bracket
if ch in bracket:
# if the stack is not empty and the top of the stack is the matching opening bracket
if stack and bracket[ch] == stack[-1]:
stack.pop()
# otherwise, we return false
else:
return False
# case 2: the character is an opening bracket
else:
stack.append(ch)
return not stack
Time Complexity and Space Complexity
The time complexity is $ O(n) $ since we are iterating through the string once.
The space complexity is $ O(n) $ since in the worst case scenario, we will have to store all the opening brackets in the stack.