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
Top comments (0)