---
title: 【LeetCode】0020. Valid Parentheses
date: 2018-12-20
is_modified: false
disqus: cynthiahackmd
categories:
- "面試刷題"
tags:
- "LeetCode"
---

{%hackmd @CynthiaChuang/Github-Page-Theme %}

<br>

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.
<!--more-->
<br>

**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

<br>

**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

<br><br>

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

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. 解題目錄](/x62skqpKStKMxRepJ6iqQQ)

<br><br>

> **本文作者**： 辛西亞．Cynthia
> **本文連結**： [辛西亞的技能樹](https://cynthiachuang.github.io/LeetCode-0020-Valid-Parentheses) / [hackmd 版本](https://hackmd.io/@CynthiaChuang/LeetCode-0020-Valid-Parentheses)
> **版權聲明**： 部落格中所有文章，均採用 [姓名標示-非商業性-相同方式分享 4.0 國際](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.en) (CC BY-NC-SA 4.0) 許可協議。轉載請標明作者、連結與出處！