DEV Community

WhereIsLijah
WhereIsLijah

Posted on

20. Valid Parentheses

We must consider that each bracket is closed in the correct order, which is vital logic we must pay attention to for our program to work.

Since this is a stack-based question, an easy way would be to represent our stack as a list and also use a mapping (dictionary) of each closing bracket to their corresponding opening brackets.

Solution:
1 - create an empty stack

2 - create a map that contains key-value pairs with the closing brackets being the key and their corresponding opening brackets being the value

3 - loop through each character in the string
3a - if the character is not Mapped (it means it is an opening bracket) then we append it to the stack and continue to the next character.

4 - else if the character is in the map then we check if the stack is empty (if it is then there's a problem because we have nothing to compare our closing brackets with) or also peek/check the most recent entry(top) into the stack and compare to the value of the current key in the Map, If they are not equal then return False.

5 - if the element matches, we pop the last entry into the stack to move to the next character/bracket.

6 - (Outside the loop) Then we return the length of the stack, if empty then it is valid, else it is invalid

    stack = []
    Map = {")":"(","]":"[","}":"{"}

    for c in s:
        if c not in Map:
            stack.append(c)
            continue
        elif c in Map:
            if len(stack) == 0 or stack[-1] != Map[c]:
                return False
            stack.pop()
    return len(stack) == 0
Enter fullscreen mode Exit fullscreen mode

Top comments (0)