【Leetcode 筆記】 20. Valid Parentheses

題目解釋

給定一個僅包含字元 '(', ')', '{', '}', '[' 和 ']' 的字串 s，確定輸入字串是否有效。

輸入字串在以下情況下有效：

1. 左括號必須由相同類型的括號封閉。
2. 左括號必須以正確的順序關閉。
3. 每個右括號都有一個對應的相同類型的左括號。

範例

• 輸入: s = "()"
• 輸出: true

輸出是 true，因為 ( 與 ) 可以配對。

最佳解法

由於這題是需要在 k 的容許範圍內替換掉字母，以讓整個 substring 的字串能夠盡可能變長。因此我們直覺的就想到建立一個 {字母: 次數} 的 dict 來維護我們 traverse 時的關係。

我們使用雙指標（Two Pointer）的解法來解這題。

NOTE: 請謹記 right - left + 1 這個公式，它就是我們滑動窗口（Sliding Window）的長度！

步驟

程式碼

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        match_pattern = {
            ')': '(',
            '}': '{',
            ']': '['
        }

        for i in s:
            if i not in match_pattern:
                stack.append(i)
            else:
                if not stack or stack.pop() != match_pattern[i]:
                    return False

        if not stack:
            return True
        else:
            return False

時間複雜度

O(n)，n 是 s 的字母個數。

空間複雜度

O(n)。

結語

Run 時覺得自己才思敏捷，
Submit 後被 edge case 搞到夜不能寐 💯

• About
• Latest Posts

數據女巫 𝔻.𝕡𝕪𝕤 🔮

𝐀𝐈 𝐀𝐫𝐭𝐢𝐬𝐭 • 𝐒𝐨𝐟𝐭𝐰𝐚𝐫𝐞 𝐄𝐧𝐠𝐢𝐧𝐞𝐞𝐫
﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊
致力於打破現有框架的 AI 藝術創作者，曾接受藝文雜誌的個人專訪，作品於香港實體展出。有擔任大學講座講師與 Stable Diffusion AI 年會講者的經驗。擅長 Live Prompting，曾獲 GIGABYTE VS AI 街頭對戰冠軍、ASUS 校園 AI 繪圖競賽亞軍等殊榮。
---
歡迎合作邀約 / 委託 / 各式交流
ᴇᴍᴀɪʟ：dpys@techmagichouse.art

Latest posts by 數據女巫 𝔻.𝕡𝕪𝕤 🔮 (see all)

• [推薦工具] 讓程式碼截圖變的美美的吧！VScode CodeSnap 與 3 種同功能線上工具介紹 - 2025-01-05
• [AI 繪圖初級教學] 用 X/Y/Z Plot 比較 Stable Diffusion 的 prompt 與 LoRA 效果 - 2024-12-27
• [AI 繪圖中級篇教學] Stable Diffusion WebUI WD14 Tagger 介紹 - 2024-12-26