Valid Parentheses

Given a string 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.

Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true

Example 2:

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

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}" 

Output: true 


Solution:

We will use stacks here. 

Algorithm:

1) If the element encountered is '{' , '[' and '(', we will push it into stack.

2) If the element encountered is ']','}' and ')', we will check if it's complement is present at the top of stack. If the complement is not present then we will return false else we will repeat steps 1 and 2.  


Time Complexity: O(n) where n is length the string.

Space Complexity: O(1)

Comments

Popular posts from this blog

Longest Common Prefix

Roman To Integer

Two Sum