LeetCode | Valid Parentheses | Facebook Interview Questions | Geek Hacker
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.
Constraints
1 <= s.length <= 104
s
consists of parentheses only'()[]{}'
Examples
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
Analysis
In order to determine that an input string is valid, all starting parenthesis must be closed by the same type of parenthesis in the correct order. Therefore, we can use a stack data structure due to its Last In First Out (LIFO) property.
We start by traversing the string from left to right. If we encounter a starting parenthesis, we push it to the stack. Then, if we encounter a closing parentheses, we check it with the top of the stack.
Algorithm
- Declare a character stack.
- Traverse the string
s
from left to right. - If the current character is a starting parenthesis, then push it to the stack.
- If the current character is a closing parentheses, then pop from the stack.
- If the popped character is the matching starting bracket, then we move further, else brackets are not balanced, so we return
False
. - At last, for valid string, the stack should be empty because all the closing parentheses should have matched with the right ones.
Python 3 Code
def isValid(self, s):
stack = []
# Traversing the Expression
for char in s:
if char in [“(“, “{“, “[“]: # Push the element in the stack
stack.append(char)
else: # IF current character is not opening
# bracket, then it must be closing.
# So stack cannot be empty at this point.
if not stack:
return False
current_char = stack.pop()
if current_char == ‘(‘:
if char != “)”:
return False
if current_char == ‘{‘:
if char != “}”:
return False
if current_char == ‘[‘:
if char != “]”:
return False # Check Empty Stack
if stack:
return False
return True
For more LeetCode problems’ solutions, visit my GitHub repo.
If you enjoyed reading this article, please recommend and share it to help others find it!