[PYTHON] Stack problem: Try to solve "20. Valid Parentheses"

Introduction

I solved the stack problem, so I made a note of it.

Try to solve "20. Valid Parentheses"

Link to problem: https://leetcode.com/problems/valid-parentheses/

answer:

class Solution:
    def isValid(self, s: str) -> bool:
      if len(s)%2 != 0:
        return False

      dic = {'(':')','{':'}','[':']'}
      stack = list()

      for i, c in enumerate(s):
        if s[i] in dic: # verify only left-bracket
          stack.append(s[i]) # add only left-bracket
        else:
          if len(stack) != 0 and dic[stack[-1]] == s[i]:
            stack.pop() # remove a last element
          else:
            return False

      if len(stack) == 0:
        return True

I will explain the flow of this process.

First, create a list called stack, a dictionary with left and right parentheses paired.

Then, look at the input character strings in order from the front, and add them to the stack in the case of left parentheses. (Only the left parenthesis is added to the stack) In the case of right parenthesis, if the last element of the stack is a paired left parenthesis, remove the left parenthesis from the stack. (If not, False is returned and the process ends)

Finally, it returns True if the stack is empty.