題目：20.Valid Parentheses（有效的括號）

題目說明

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

有效的條件：

1. 左括號必須由相同型別的右括號關閉。
2. 左括號必須以正確的順序關閉。

範例：

Input: s = "()"
Output: true

Input: s = "()[]{}"
Output: true

Input: s = "(]"
Output: false

Input: s = "([)]"
Output: false

Input: s = "{[]}"
Output: true

解法思路（Stack 堆疊法）

1. 使用一個堆疊 stack 來存放左括號。

2. 遍歷字串：

   • 遇到左括號就放進 stack。
   • 遇到右括號時，檢查 stack 是否為空，且最上層是否與它匹配：
     • 如果不匹配 → 回傳 false。
     • 如果匹配 → 把最上層括號移除（pop）。

3. 遍歷結束後，如果 stack 為空，則字串有效，否則無效。

複雜度分析
時間複雜度：O(n)（遍歷一次字串）
空間複雜度：O(n)（最壞情況所有都是左括號）

程式碼

import java.util.Stack;

public class Solution {
public boolean isValid(String s) {
Stack stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(') {
stack.push(')');
} else if (c == '{') {
stack.push('}');
} else if (c == '[') {
stack.push(']');
} else {
if (stack.isEmpty() || stack.pop() != c) {
return false;
}
}
}
return stack.isEmpty();
}
}

Python 解法

def isValid(s):
stack = []
mapping = {')': '(', '}': '{', ']': '['}

for c in s:
    if c in mapping:  # 如果是右括號
        top = stack.pop() if stack else '#'
        if mapping[c] != top:
            return False
    else:  # 左括號
        stack.append(c)

return not stack

Java 與 Python 差別

Java 用 Stack，並且必須明確宣告型別；Python 則是用 list 當作 stack，透過 .append() 和 .pop() 來操作，語法更簡單。
此外，Java 要寫 for (char c : s.toCharArray()) 來轉成陣列迭代，而 Python 可以直接 for c in s。

心得

這題的關鍵不是數學，而是資料結構的應用 —— Stack（堆疊）。
一開始我有點困惑：「程式怎麼知道哪個括號要先配對？」後來才發現，堆疊的「先進後出」特性剛好符合括號匹配的需求。當我讀到一個左括號時，先把它丟進堆疊，等遇到右括號時，就檢查堆疊最上面的元素是否能匹配，如果不行就立刻判斷失敗。
Java 的解法比較嚴謹，要先建一個 Stack，然後用 push() 和 pop() 來操作；Python 就簡單很多，用 list 搭配 append() 與 pop() 就能完成。而且 Python 的 for c in s 迴圈很直觀，不用像 Java 還要 .toCharArray()。讓我感受到不同語言在語法設計上的風格差異：Java 偏向完整結構，Python 則強調快速直覺。
如果只靠暴力檢查字串裡的每個括號，會很難處理順序問題。但用 stack 就能自然地解決，程式碼也變得很乾淨。雖然程式看起來不長，但背後的思維其實很重要：要善用資料結構的特性去簡化問題。