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:

1. Open brackets must be closed by the same type of brackets.
2. 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

1. Declare a character stack.
2. Traverse the string s from left to right.
3. If the current character is a starting parenthesis, then push it to the stack.
4. If the current character is a closing parentheses, then pop from the stack.
5. If the popped character is the matching starting bracket, then we move further, else brackets are not balanced, so we return False.
6. 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!