DEV Community


Posted on

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!


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


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.


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
        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.

Top comments (0)