Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: True

Example 2:

Input: "()[]{}"
Output: True

Example 3:

Input:** "(]"
**Output:** false

Example 4:

Input:"([)]"
Output: False

Example 5:

Input: "{[]}"
Output: True

Related Topics: String、Stack

解題邏輯與實作

這題是在驗證括號是否成對，看到這種題目第一反應就是用 Stack：

1. 依序遍歷輸入字串
   1. 若為左括號，則 push 進入 stack
   2. 若為右括號，則
      1. 若 Stack 為空，則回傳 False
      2. 若 Stack 不為空，則取出 Stack 頂端元素，判斷是否成對，若不成對則回傳 False，反之繼續向下執行。
2. 直到字串遍歷完畢，且 Stack 為空，則回傳 True，反之回傳 False。

class Stack(object):
   def __init__(self):
      self.stack=[]
   def isEmpty(self):
      return self.stack==[]
   def push(self,item):
      self.stack.append(item)
   def pop(self):
      if self.isEmpty():
         raise IndexError
      return self.stack.pop()
   def peek(self):
      return self.stack[-1]
   def size(self):
      return len(self.stack)
      
class Solution:
   def isValid(self, s: str) -> bool:
      match = {")":"(", "}":"{","]":"["}

      stack = Stack()
      legal = True
            
      for c in s:
         if c in match.values():
            stack.push(c)
         elif c in match.keys():
            if stack.isEmpty():
               legal=False
               break
            else:                              
               if match[c] !=   stack.pop():
                  legal = False
                  break
         else :
               legal=False
               break
                              
      if not stack.isEmpty():
         legal = False
            
      return legal

依照題目的輸入限制，進一步優化與精簡程式碼：

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

      for c in s:
         if c in match:
            if stack == [] or match[c] !=   stack.pop():
               return False
         else:
            stack.append(c)

      return stack == []

其他連結

1. 【LeetCode】0000. 解題目錄

本文作者： 辛西亞．Cynthia
本文連結： 辛西亞的技能樹 / hackmd 版本
版權聲明： 部落格中所有文章，均採用 姓名標示-非商業性-相同方式分享 4.0 國際 (CC BY-NC-SA 4.0) 許可協議。轉載請標明作者、連結與出處！