[LeetCode] 20. Valid Parentheses

1. Description

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

 

An input string is valid if :

 

• Open bracket must be closed by the same type of brackets
• Open brackets must be closed in the correct order.
• Every closed bracket has a corresponding bracket of the same type.

 

constraints :

• 1 <= s.length <= \(10^4\)
• s consists of parentheses only '()[]{}'.

 

2. Algorithms

In this problem, the open bracket must be closed to the corresponding close bracket. So we can map all brackets into dictionary in key(open bracket) : value(close bracket).

 

The stack data structure will be used in this problem. For each element of the input string s, if the element is an open bracket, push the corresponding close bracket to stack. And if the element is an close bracket, check the last element of stack is same with the current close bracket.

 

s = "()[]{}", stack = []

iteration1 : s[i] = ( -> push to stack [')']
iteration2 : s[i] = ) -> check if the current element is same with stack[-1] 
                 if True, pop the stack

 

1. Start
2. Declare variable named brackets
3. Update key(open bracket) : value(close bracket) to brackets
4. Declare variable named stack and initialize it to empty list(stack)
5. Repeat the steps through the elements of s
   1. If the element is open bracket, push the corresponding close bracket to stack.
   2. If the element is close bracket, compare it to the last element of stack
      1. If there is any element in stack and two are same, pop the stack
      2. Else, return False
6. Return if the length of stack is 0
7. End

 

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 stack and c == stack[-1]: 
                    stack.pop() 
                else: 
                    return False 

        return len(stack) == 0

 

4. Conclusion

 

Time Complexity : \(O(N)\)

Space Complexity : \(O(1)\)