[LeetCode] 20.Valid Parentheses (Easy/Python)

Valid Parentheses - LeetCode

Above is a link to the problem.

 

There is a string consist of (, {, [, ), } and ]

Open Bracket - (, {, [ must be closed by the same type of close brackets - ), }, ] and in the correct order.

If the string satisfies the above condition then return True.

If not, then return False.

 

For example,

({}) : True / () : True / (){}[] : True / (){[]} : True

)) : False / [{]} : False / {[(}]) : False

 

When I met this problem, I tried to solve this by counting each bracket.

But it was not good to solve this problem easily.

There is lots of exception case like (}{), {([})], etc...

 

I get some advice that using the principle of the stack.

LIFO: Last In First Out

I wrote the below code.

 

 

 

Get the brackets one by one from s and if it is an open bracket append to the list L.

If it is a close bracket, it is compared with the last element of the list L to see if it is a matching close bracket.

If it is the corresponding open bracket then the last element is deleted from the list L by pop func, otherwise, False is output.

If the loop goes through the end and the list becomes an empty list, True is output.

 

 

This code gets the top 90.91% of time efficiency and the top 73.53% of space efficiency.