題目
#

leetcode 20 - Valid Parentheses (題目說明請點連結)

題目簡述
#

檢查括號是否成對匹配且順序正確。

範例
#

Example 1:

Input: s = "()"
Output: true
Explanation: 括號成對匹配且順序正確。

Example 2:

Input: s = "()[]{}"
Output: true
Explanation: 所有括號都成對匹配且順序正確。

Example 3:

Input: s = "(]"
Output: false
Explanation: 括號不匹配，'(' 和 ']' 不是對應的括號。

解題思路
#

題目要求檢查括號是否成對匹配並且順序正確。有效的括號必須滿足以下條件：

只有三種括號類型：()，[]，{}。
每個開括號都必須有對應的閉括號，並且順序必須正確。
如果所有括號都正確匹配，則返回 true，否則返回 false。

這個問題可以使用 Stack（堆疊） 來解決，因為堆疊是後進先出的結構，適合處理嵌套的結構。

解法
#

遍歷字串中的每個字元：
- 如果是開括號 (、[、{，則壓入堆疊。
- 如果是閉括號 )、]、}，則檢查堆疊頂端是否是對應的開括號，如果是則彈出。
- 如果不是對應的開括號或堆疊為空，則返回 false。
遍歷結束後，檢查堆疊是否為空，若為空則表示所有括號匹配，返回 true，否則返回 false。

例子說明
#

s = "()[]{}"

初始情況：stack = []

處理第一個字元 (：
- 是開括號，壓入堆疊，stack = ['(']
處理第二個字元 )：
- 是閉括號，檢查堆疊頂端是否為對應的開括號 (
- 匹配成功，彈出堆疊，stack = []
處理第三個字元 [：
- 是開括號，壓入堆疊，stack = ['[']
處理第四個字元 ]：
- 是閉括號，檢查堆疊頂端是否為對應的開括號 [
- 匹配成功，彈出堆疊，stack = []
處理第五個字元 {：
- 是開括號，壓入堆疊，stack = ['{']
處理第六個字元 }：
- 是閉括號，檢查堆疊頂端是否為對應的開括號 {
- 匹配成功，彈出堆疊，stack = []
遍歷結束：
- 堆疊為空，返回 true

完整程式碼
#

java

import java.util.Stack;

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>(); // 初始化堆疊來存儲開括號

        for(int i = 0; i < s.length(); i++) { // 遍歷字串中的每個字元
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') { // 如果是開括號
                stack.push(c); // 壓入堆疊
            } else if (!stack.isEmpty() && c == ')' && stack.peek() == '(') { // 如果是右括號且堆疊頂端是對應的左括號
                stack.pop(); // 彈出堆疊頂端元素
            } else if (!stack.isEmpty() && c == ']' && stack.peek() == '[') { // 如果是右方括號且堆疊頂端是對應的左方括號
                stack.pop(); // 彈出堆疊頂端元素
            } else if (!stack.isEmpty() && c == '}' && stack.peek() == '{') { // 如果是右大括號且堆疊頂端是對應的左大括號
                stack.pop(); // 彈出堆疊頂端元素
            } else { // 如果括號不匹配或堆疊為空
                return false; // 返回 false
            }
        }

        return stack.isEmpty(); // 檢查堆疊是否為空，如果為空則所有括號都匹配
    }
}