題目資訊

題目編號: 20
題目連結: Valid Parentheses
主題: String, Stack

題目敘述

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

當輸入字串滿足以下條件時，為有效字串：

開括號必須由同類型的括號關閉。
開括號必須以正確的順序關閉。
每一個閉括號都有一個對應的同類型開括號。

範例 1:

輸入: s = “()”

輸出: true

範例 2:

輸入: s = “()[]{}”

輸出: true

範例 3:

輸入: s = “(]”

輸出: false

範例 4:

輸入: s = “([])”

輸出: true

限制條件:

$1 \leq s.length \leq 10^4$
$s$ 僅由括號 '()[]{}' 組成。

直覺

此問題需要驗證一個僅包含不同類型括號的字串是否有效。一個有效的字串是指每一種開括號都由同類型的關括號在正確的順序中閉合。這樣的直覺暗示需要一種機制，以便在從左到右處理字串時追蹤未匹配的開括號。堆疊(Stack)資料結構非常適合這個目的，因為它遵循後進先出(Last In, First Out, LIFO)的原則，這與將最近打開的括號與對應的關括號匹配的要求相吻合。

解法

所給的 C++ 解法利用堆疊來驗證字串中的括號序列。其策略涉及遍歷字串中的每一個字元：

處理開括號： 對於遇到的任何開括號（'(', '{', '['），將預期的對應關括號（')', '}', ']'）推入堆疊中。這樣就能準備好堆疊來驗證接下來的關括號。
驗證關括號： 當遇到關括號時，演算法會檢查：
- 如果堆疊是空的，這表明沒有可用的開括號來配對，因此輸入的字串無效。
- 如果堆疊不為空，則將堆疊的頂部（包含預期匹配最近未匹配的開括號的關括號）與當前的關括號進行比較。如果它們不匹配，則表示括號類型不匹配，並且輸入字串無效。
最終驗證： 在遍歷字串結束時，如果每一個開括號都已經與對應的關括號匹配，則堆疊應該是空的。堆疊為空表示括號序列是完全平衡且有效的。

通過這種方法，演算法有效地使用堆疊檢查平衡且正確嵌套的括號，確保每個關括號都匹配最近未匹配的開括號。這種解法通過對每個字元僅處理一次，達到線性時間複雜度 $O(n)$，其中 $n$ 是字串的長度。

程式碼

C++

class Solution {
public:
    bool isValid(string s) {
        stack<char> bracketStack;
        
        for (char currentChar : s) {
            // 將每個開括號對應的預期關閉括號推入堆疊
            if (currentChar == '(') {
                bracketStack.push(')');
            } else if (currentChar == '[') {
                bracketStack.push(']');
            } else if (currentChar == '{') {
                bracketStack.push('}');
            } 
            // 如果找到一個關括號，檢查其是否有匹配的開括號
            else {
                if (bracketStack.empty() || currentChar != bracketStack.top()) {
                    return false; // 沒有匹配的開括號或不匹配
                }
                bracketStack.pop(); // 彈出匹配的開括號
            }
        }

        // 如果所有開括號都有匹配的關括號，則堆疊應為空
        return bracketStack.empty();
    }
};

Python

class Solution:
    def isValid(self, s: str) -> bool:
        bracketStack = []

        for currentChar in s:
            # 將預期的關閉括號推入堆疊，對於每個開啟括號
            if currentChar == '(':
                bracketStack.append(')')
            elif currentChar == '[':
                bracketStack.append(']')
            elif currentChar == '{':
                bracketStack.append('}')
            # 如果找到一個關閉括號，檢查是否有相符的開啟括號
            else:
                if not bracketStack or currentChar != bracketStack[-1]:
                    return False  # 沒有相符的開啟括號或不匹配
                bracketStack.pop()  # 移除相符的開啟括號

        # 如果所有開啟括號都有相符的關閉括號，則堆疊應為空
        return not bracketStack

複雜度分析

時間複雜度: $O(n)$

時間複雜度是 $O(n)$，其中 $n$ 是輸入字串 s 的長度。這是因為我們在 for 迴圈中逐一遍歷字串中的每個字符，對每個字符執行恆定數量的工作（無論是推入或彈出堆疊）。

空間複雜度: $O(n)$

空間複雜度在最壞的情況下是 $O(n)$。在所有字符都是開括號的情況下，我們會將所有字符推入堆疊，導致最大堆疊大小與輸入大小 $n$ 成正比。然而，在一般情況下，堆疊所使用的空間取決於未匹配的開括號數量，但其仍受限於 $n$。

CS Note
En

Leetcode 20. Valid Parentheses

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析