前言

今天要解的題目是 Valid Parentheses（有效的括號）。
題目要求我們判斷一個只包含括號的字串是否是有效的。

有效的意思是：每個開括號必須有對應的閉括號，並且它們的順序必須是正確的。
這道題目很常見，是面試中的常客哦～那我們來看看怎麼解決這個問題吧！

英文題目

Valid Parentheses

難度：Easy

題目描述：

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

給定一個只包含括號 ()、{} 和 [] 的字串 s，判斷該字串是否是有效的。

有效的字串需要滿足：

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

範例 1：

輸入： s = "()"

輸出： true

範例 2：

輸入： s = "()[]{}"

輸出： true

範例 3：

輸入： s = "(]"

輸出： false

思路

這道題的關鍵是處理括號的嵌套和順序。我們可以使用堆疊來追蹤左括號，當遇到右括號時，從堆疊中彈出對應的左括號進行匹配。

具體思路：

1. 使用堆疊：當遇到左括號 (、{、[ 時，將它們壓入堆疊；當遇到右括號 )、}、] 時，檢查堆疊是否有相應的左括號可以匹配。

2. 匹配括號：如果堆疊不為空且匹配成功，繼續處理；否則，如果不匹配或者堆疊為空，返回 false。

3. 檢查堆疊是否清空：最後，如果堆疊中還有多餘的左括號，則說明有未匹配的左括號，返回 false。如果堆疊為空，說明所有的括號都匹配成功，返回 true。

實作

function isValid(s: string): boolean {
    const stack: string[] = []; // 堆疊用來追蹤左括號
    const map: { [key: string]: string } = {
        ")": "(",
        "}": "{",
        "]": "["
    };

    // 遍歷字串中的每一個括號
    for (let char of s) {
        if (char === "(" || char === "{" || char === "[") {
            // 如果是左括號，壓入堆疊
            stack.push(char);
        } else {
            // 如果是右括號，檢查是否與堆疊頂部的左括號匹配
            const top = stack.pop();
            if (top !== map[char]) {
                return false; // 如果不匹配，返回 false
            }
        }
    }

    // 如果堆疊為空，則所有括號都匹配成功
    return stack.length === 0;
}

解題心法

1. 使用堆疊的原因：

   • 堆疊是一種「後進先出」（LIFO）的數據結構，這正好符合括號匹配的需求。
   • 當我們遇到右括號時，需要檢查它對應的左括號是否是最近的一個開括號，這就能用堆疊來解決。

2. 匹配括號的邏輯：

   • 當我們遇到右括號時，從堆疊中彈出最近的一個左括號，檢查它是否與當前右括號匹配。如果匹配則繼續，如果不匹配則直接返回 false。

3. 檢查最終狀態：

   • 當我們處理完所有的括號後，檢查堆疊是否為空。如果還有剩餘的左括號在堆疊中，說明它們沒有匹配的右括號，應該返回 false。如果堆疊為空，說明所有的括號都正確匹配，返回 true。

為什麼這樣處理？

這樣處理的核心是堆疊，它能夠完美模擬括號的嵌套結構，每當我們遇到右括號時，能夠正確匹配最近的左括號。通過這種方式，我們可以在 O(n) 的時間內處理這個問題，而空間複雜度取決於堆疊的大小，最壞情況下是 O(n)。

本次要點：

• 堆疊：用來追蹤左括號，當遇到右括號時進行匹配。
• 檢查匹配：每次彈出堆疊中的左括號，檢查是否與當前右括號匹配。
• 堆疊為空：最後堆疊為空，代表所有括號都正確配對，否則返回 false。

這道題是不是很有趣呢？
透過堆疊這個小工具，我們可以輕鬆解決括號配對的問題。
希望你能理解這個解法並靈活運用！
我們下次再來挑戰更多有趣的題目吧！