【第三天 - Stack 题目分析】

先简单回顾一下，今天预计分析的题目：

1. Valid Parentheses
昨天问到，如果 ([)] 是错误的，那什麽是正确的 ?
- 你写 ()[] 或 [()] 或 ([]) 都可以，在你遇到右括号时，对应的左括号，都是 same type 就可以
  - 例如 ( 对 ) 就是 same type， ( 对 ] 就不是 same type
在小学数学运算中，{}是大括号，[]是中括号，()是小括号，优先顺序为小括号 > 中括号 > 大括号，那这一个题目，遇到 ([{}]) 这样的情况，是不是也是可接受的 ?
- 可以的，长大後，我们已经较少使用 [] 跟 {} 做为算式的一部分，大部分数学中的运算都是全部使用 () ，然後依照最内部的括号依序做运算
- 中括号与大括号，在数学中有其他涵义，例如大括号常做为集合，中括号可表示高斯符号
根据观察，我们是不是平常数学式中，遇到右括号，就会去找与之对应的左括号
所以程序整体逻辑很简单：
1. 我们一个个读 s 中的每个字元，例如 s 为 {}，那我们先读 {，再读 }
  - PS: 这样 { 我们会称为字元，超过一个字元组成，就会变成字串，例如{}，会组成字串
2. 字元遇到左括号，我们就先用 stack 盒子存起来，若字元为右括号，就把刚刚存起来的左括号拿出来比对是不是 same type
  - PS: ( 对 ) 就是 same type，( 对 ] 或 } 就不是 same type，以此类推
3. 当每个字元都读完，最後我们再来检查看看 stack 是不是都空了，如果都空了，就代表他左右括号数量一样，那就回传 True，反之就回传 False
  - 之所以要检查，就是怕若 s 为 (()，那在前面两个步骤中，stack 盒子会装 ((，但是只遇到一次 )，只拿出一次(，所以盒子内还会有一个 (
不专业程序流程图，请依照步骤慢慢对照： (菱形为判断式；长方形为程序一般执行，可能储存变数等..；平行四边形为输入与输出；圆角长方形代表程序的开始或结束)
课间小Q&A：
- 若变数 s 为 {}{}()[[]] ，stack 盒子会依序装入哪些字元? 是否回传 True?
  1. 曾经依序装入 {{([[
    1. 先装入 {，遇到 } 又把{拿出来了，所以stack 为空
    2. 再装入 {，遇到 } 又把{拿出来了，所以stack 为空
    3. 再装入 (，遇到 ) 又把(拿出来了，所以stack 为空
    4. 再依序装入 [[，遇到 ] 把一个 [ 拿出来了，所以stack 里面还有一个 [，接着又遇到 ]，又把stack 内的 [ 拿出来，此时 stack 为空
  2. 因为每次遇到右括号都是 same type，加上最後 stack 是空的，代表左右括号数量一样，所以回传 True
python 一般写法 (比较没有弹性) ( 时间复杂度为 O(n) → 就是全部 s 长度跑一次 )

class Solution:
    def isValid(self, s: str) -> bool:
#       先宣告一个 stack 盒子，之後专门存放左括号
        stack_left = []
#       把变数 s 一个个读字元，每一次读的字元存在 chr 变数中
        for chr in s:
#           若 chr 为左括号
            if chr == "(" or chr == "[" or chr == "{":
                stack_left.append(chr)
#           若 chr 不是左括号  (chr 为右括号)
            else:
#               若 stack 内还有东西 (因为要拿一个 stack 盒子中的左括号，出来跟右括号比对是否为 same type)
                if stack_left:
#                   stack 盒子拿出来的左括号放在 left 变数中
                    left = stack_left.pop()
#                  接下来三个判断式，依序判断是否为 same type，一旦不是就直接回传 False
                    if chr == ")" and left != "(":
                        return False
                    elif chr == "]" and left != "[":
                        return False
                    elif chr == "}" and left != "{":
                        return False
#               若都读到右括号了，但是 stack 没有左括号可以配对，那就直接回传 False 
                else:
                    return False
#       判断 stack 是否为空，stack若是空的 为 True
#       stack 内有东西
        if stack_left:
            return False
#       stack 内没有东西了~
        else:
            return True

若程序想要更有弹性，可能之後不只()[]{}这几种符号，那我们可以把比对 same type 写成 dictionary 的结构 ( 时间复杂度为 O(n) → 就是全部 s 长度跑一次 )

class Solution:
    def isValid(self, s: str) -> bool:
        stack_left = []
        dict = {")": "(", "]": "[", "}": "{"}
        for chr in s:
#           若 chr 为 左括号
            if chr in dict.values():
                stack_left.append(chr)
#           若 chr 为 右括号
            elif chr in dict.keys():
#               若 stack 盒子是空的、没有对应到 same type，回传 False
                if len(stack_left) == 0 or dict[chr] != stack_left.pop():
                    return False
            else:
                return False
            
        return not stack_left

<<: 前後端分离

>>: 【Day3】声音的特徵提取