Day 5：20. Valid Parentheses

今日题目

题目连结：20. Valid Parentheses
题目主题：String, Stack

玩了几题排序後，接下来会分享两种重要的资料结构Stack & Queue，今天选的题目是很典型的Stack题目。

简单说说 Stack

Stack（堆叠）是一种後进先出 ( LIFO ) 的资料结构，新增资料永远从後面进去，取出资料永远从最後面资料取出，使用的方式及过程如下图。

可以想像 Stack 是一个圆角方形空间，以图中范例来看，如果有一个新的值进去这个空间，一定会从最後面进去放在最後一个位置。每一次取出时也是从最後面取出，不能随便从其他位置取出。

题目解说

建议可以看看LeetCode原本的题目说明，这边是用我的方式说明题目，参考就好。

本题的目标是确认一个字串中是否有平衡的出现 () , {} , [] 三种括号，开括号要由相同类型的括号关闭，有平衡的话就回传 True。若出现不平衡的状况，如 : (] , [} , {()] ,，就会回传False。这题建议看范例比较好理解。

约束：

• 1 <= s.length <= 104
• 字串是由'() [] {}'组成的

范例1

输入: s = "()"
输出: true

范例2

输入: s = "()[]{}"
输出: true

范例3

输入: s = "(]"
输出: false
解释: 以 '(' 开头应该要由 ')' 结尾，但范例是 ']' 结尾，因此这题回false。

范例4

输入: s = "([)]"
输出: false
解释: 以 '([' 开头，後面应该要出现的关闭顺序应为 '])' 才能平衡配对，但范例是 ')]'，因此这题回false。

范例5

输入: s = "{[]}"
输出: true
解释: 以 '{[' 开头，後面关闭的顺序也是 ']}'，有达到平衡配对，因此这题回true。

建议到这边先停下来，尝试自己解解看，若没有想法可再继续走下去。

解题的想像

文字描述

1. 宣告一个stack
2. 跑一个回圈每一圈检查一个字元
   • 遇到一个开括号就放进stack中
   • 遇到一个关括号就从stack取出一笔资料检查是否有配对成功
     • 若没有配对成功直接回传False结束
     • 若有配对成功继续往下个字元检查
3. 最终如果stack是空的，代表都有配对到是平衡的，回传True

图解过程

范例: s = "{[]}"

可以把s想像成图中最上方的阵列，每一圈取一个字元来处理。先看第一圈我们取到 '{' 因为是开括号，直接放到stack中。再来直接看到第三圈取到了关括号 ']'，需要从stack取得最後进去的开括号来做配对，有成功配对成'[]'，继续处理。最後这个范例因为能清空stack，因此输出为True。

若因为没想法而走到这边，建议看完想像以後再给自己一次机会试一次。

程序码撰写

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for c in s:
            # 遇到开括号，将值放入stack中。
            if c == '{' or c == '[' or c == '(':
                stack.append(c)
            # 遇到关括号，跟stack确认是否有配对到。
            else:
                if not stack: return False
                open = stack.pop()
                if c == '}' and open == '{': continue
                elif c == ')' and open == '(': continue
                elif c == ']' and open == '[': continue
                else: return False
        return not stack

希望您今天能了解到...

1. Stack基础概念
2. 20. Valid Parentheses 解题方法

若内容有什麽问题或建议欢迎一起交流：）
感谢您今天愿意花时间看完这篇文章~~~~

Next：232. Implement Queue using Stacks