[LeetCode][python3]0020. Valid Parentheses

Start the Journey
N2I -2020.04.02

1. My first solution

  1. class Solution:
  2.     def isValid(self, s: str) -> bool:
  3.         upper=['s']
  4.         for item in s:
  5.             if item in ['(','[','{']:
  6.                 upper.append(item)
  7.             if item==')':
  8.                 if upper.pop(-1)!='(':
  9.                     return False
  10.             if item==']':
  11.                 if upper.pop(-1)!='[':
  12.                     return False
  13.             if item=='}':
  14.                 if upper.pop(-1)!='{':
  15.                     return False
  16.         if upper==['s']:
  17.             return True
  18.         return False

Explanation:

The solution use a buffer to solve this problem. For the elements ['(','[','{'], has to be matched in the sequence “Last in, First out”. And the element ['s'] to check if buffer is empty.


2. A clean solution

  1. class Solution:
  2.     def isValid(self, s: str) -> bool:
  3.         mapping = {')':'(', '}':'{', ']':'['}        
  4.         stack = []        
  5.         if not s:
  6.             return True       
  7.         for ele in s:
  8.             if ele in mapping:
  9.                 if stack:
  10.                     top = stack.pop() 
  11.                 else:
  12.                     top = '$'
  13.                 if top != mapping[ele]:
  14.                     return False
  15.             else:
  16.                 stack.append(ele)        
  17.         return not stack

Explanation:

A more flexible way to code the script.