題目說明

20. Valid Parentheses II
    給你一個只包含 '('、')'、'{'、'}'、'['、']' 的字串，請判斷括號是否 有效。
    有效的括號需滿足：
    1. 左括號必須由相同類型的右括號閉合。
    2. 左括號必須以正確順序閉合。

範例

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

Input: "([)]"
Output: false

Input: "{[]}"
Output: true

程式碼

Python 解法

def isValid(s: str) -> bool:
stack = []
mapping = {')':'(', '}':'{', ']':'['}
for char in s:
if char in mapping:
top = stack.pop() if stack else '#'
if mapping[char] != top:
return False
else:
stack.append(char)
return not stack

Java 解法

import java.util.*;
class Solution {
public boolean isValid(String s) {
Stack stack = new Stack<>();
Map<Character, Character> mapping = new HashMap<>();
mapping.put(')', '(');
mapping.put('}', '{');
mapping.put(']', '[');

    for (char c : s.toCharArray()) {
        if (mapping.containsKey(c)) {
            char top = stack.isEmpty() ? '#' : stack.pop();
            if (mapping.get(c) != top) return false;
        } else {
            stack.push(c);
        }
    }
    return stack.isEmpty();
}

}

Java vs Python 差異
• Python 用 list 當 stack，Java 用 Stack 類別
• Python 用字典 mapping，Java 用 HashMap
• 核心邏輯相同：遇到右括號就檢查 stack 是否匹配，最後檢查stack 是否清空

複雜度分析
• 時間複雜度：O(n)，每個字元最多進入或退出 stack 一次
• 空間複雜度：O(n)，最壞情況下 stack 需要存放所有左括號