Valid Parentheses

This is a part of my series where I memo learning from LeetCode. If you have better solutions or ideas, please leave a comment!

Problems

Valid Parentheses

We have to check the given string is valid parentheses.
The given string is invalid when there is a lacking of right or left parenthesis or the order of parentheses is wrong.

For example,

"([])" -> OK
"()[]{}" -> OK
"[](()" -> NG
"([)]" -> NG
"]" -> NG

Approach

Stack and map are useful for this question.

We are gonna look the given string in order from the front.

When the char is the left side parenthesis, add it to stack, and when the char is the right side parenthesis, pop stack top value and check whether is valid or not by using map.
So we have to set the map as below,

parentheses_map = [")":"(", "}":"{", "]":"["]

Finally, if stack is empty, the string is valid.

Solution

class Solution:
    def isValid(self, s: str) -> bool:

        stack = []

        parentheses_map = {")":"(", "}":"{", "]":"["}

        for i in s:
            if i in parentheses_map:
                stack_top = stack.pop() if stack else ' '
                if parentheses_map[i] != stack_top:
                    return False
            else:
                stack.append(i)
        return not stack

Note: In the above Solution code, when the stack is empty, we have to assign a dummy value because if write as below,

if stack:
    stack_top = stack.pop()

the case s = "]" are gonna be True and this is a wrong answer.

Thank you for reading this article!
I always welcome your feedback, question, and idea.