1 題目描述

這是一個括號匹配的問題，給一個只包含(, ), {, }, [, ]的字符串，目的是要檢查一個字串是否是有效的括號組合。

2 解法

我的想法很簡單：

  1. 先建立一個 dictionary，把所有的括號對應關係記錄下來。 key 是 (, {, [，value 是說明 key 的方向(open or close)與屬性(大, 中, 小括號)。
  2. 開始遍歷字串，如果是open，就把它放進 stack 裡面，如果是close，就檢查 stack 最上面的元素是否是對應的開括號，如果是就 pop 掉，不是就返回 False。

大概是這種感覺：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def isValid(self, s: str) -> bool:
        str_dic = {
            "{": ["open", "Big"],
            "}": ["close", "Big"],
            "[": ["open", "Mid"],
            "]": ["close", "Mid"],
            "(": ["open", "Small"],
            ")": ["close", "Small"],
        }
        stack = []

        for i in s:
            target = str_dic.get(i)
            # open 
            if target[0] == "open":
                stack.append(i)
            else: # close
                # 應對可能一開始就是 close 的情況 stack 是空的
                if len(stack) == 0:
                    return False
                # [1] 檢查是否相同型態:  Big, Mid, Small 
                if str_dic.get(stack.pop())[1] != target[1]:
                    return False
        # 確保所有的都配對完
        return not stack # if the stack is empty, all opening brackets have been matched with their corresponding closing brackets,
                         # so the string is valid, otherwise, there are unmatched opening brackets, so return false

時間複雜度O(n) for 循環遍歷整個 s 列表，時間複雜度為 O(n)。
空間複雜度O(n) 空間複雜度由字典 stack存儲 n 個不同的字，因此空間複雜度為 O(n)。

3 總結

這題很簡單，但是要能夠想到用 stack 來解決，如果是應對對稱性的問題，stack 是一個很好的選擇。