20. Valid Parentheses Leetcode Solution

Valid Parentheses Leetcode 20 Solution

Return boolean indicating wether the pairs of paranthesis are matching and there are no un-matched paranthesis found.

Using a list to implement a stack in Python.
Store all the pairs of opening and closing tags in a dictionary. Closing brackets are the key.
Go thru the characters of the string and add / remove items when they are found in the dictionary.

Example input: (([)):
( – add;
( – add;
[ – add;
) – found in dictionary – copare to last char added <)> = unmatched = false

Example input: ()([]):
( – add;
) – found in dictionary – compares dictionary value to last added <(> == ( = true – remove last item from stack. (
( – add;
[ – add;
] – found in dictionary – compares dictionary value to last added <[> == [ = true – remove last item from stack. [
) – found in dictionary – compares dictionary value to latest in the stack <(> == ( = true – remove last item from stack. (
stack is empty, string is finished = true; if any chars are left in the stack = false;

Test Code – Python 3

import time
start_time = time.time()
def main():
    print("start")

    s = "({[]})"
    print ("s: " + s)
    
    sol = Solution()
    result = sol.isValid(s)
    print("result is: "+ str(result))
    print("end")    

class Solution:
    def isValid(self, s: str) -> bool:
        pairs = {
            ")": "(",
            "}": "{",
            "]": "["
        }
        stack = []

        for si in s:
            if si not in pairs:
                stack.append(si)
            else:
                if len(stack) == 0 or pairs[si] != stack.pop():
                    return False
        return len(stack) == 0
        

if __name__ == "__main__":
    main()
print("--- %s ms ---" % int(((time.time() - start_time)*1000)))

Test Output

start
s: ({[]})
result is: True
end
>>>