# 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: (([)):
) – found in dictionary – copare to last char added <)> = unmatched = false

Example input: ()([]):
) – found in dictionary – compares dictionary value to last added <(> == ( = true – remove last item from stack. (
] – 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
>>> ``````

Posted

in

by