【LeetCode】0020. Valid Parentheses

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




解題邏輯與實作

這題是在驗證括號是否成對,看到這種題目第一反應就是用 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 == []





[LeetCode] 解題目錄 -> 這裡走

留言

這個網誌中的熱門文章

用Markdown寫Blogger文章

【Vue.js 學習筆記】02. 基礎 Vue 概述