This content originally appeared on DEV Community and was authored by WhereIsLijah
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
This content originally appeared on DEV Community and was authored by WhereIsLijah
WhereIsLijah | Sciencx (2024-07-29T14:28:05+00:00) 20. Valid Parentheses. Retrieved from https://www.scien.cx/2024/07/29/20-valid-parentheses/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.