20 Valid Parentheses

1. Description

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if :

1. Open bracket must be closed by the same type of brackets.

2. Open bracket must be closed in the correct order.

 

constraints :

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.

2. Algorithms

Let's see the condition 1. Open bracket must be closed by the same type of brackets. we will use dictionary and stack to solve this problem. In python, we can use list for constructing stacks.

 

1. Store brackets in dictionary by open : close brackets pairs.
2. Initialize empty stack to store elements of s.
3. For each bracket from s,
   1. Append close bracket to stack if bracket is in dictionary.
   2. In case of close bracket, check if stack is not empty and bracket is same as element of stack.
      1. In case of 3.2 case, return False
      2. Else, pop the value from stack
4. Return if stack is empty state.

Algorithms will takes O(N) time complexity.

 

3. Codes

class Solution:
    def isValid(self, s: str) -> bool:
        brackets = {'(' : ')', '{' : '}', '[' : ']'}
        stack = [] 
        
        for c in s : 
            if c in brackets : 
                stack.append(brackets[c]) 
            else : 
                if not stack or c != stack[-1] : 
                    return False 
                else : 
                    stack.pop() 
        
        return len(stack) == 0

4. Conclusion