20. Valid Parentheses

題目網址：https://leetcode.cn/problems/valid-parentheses/

題意：給一只包含 '('、')'、'{'、'}'、'['、']' 的 string s, 判斷 s 是否有效。

有效的定義如下：

• 左括號必須有相同類型的右括號閉合
• 左括號必須以正確的順序閉合
• 每個右括號都有一個對應的相同類型之左括號

Solution：

想法：利用 Stack

class Solution {
public:
    bool isValid(string s) {
        if (s.size() % 2 == 1) {
            return false;
        }

        stack<char> stk;
        for (const auto& ch : s) {
            if (pairs.find(ch) != pairs.end()) {
                if (stk.empty() || stk.top() != pairs[ch]) {
                    return false;
                }
                stk.pop();
            } else {
                stk.emplace(ch);
            }
        }

        return stk.empty(); // 若 stack 為空, 則代表有效
    }

private:
    unordered_map<char, char> pairs = {
        {')', '('},
        {'}', '{'},
        {']', '['}
    };
};

• time：$O(n)$ ➔ 遍歷 s, 其中 n 為 s 的長度
• space：$O(n)$ ➔ stack 中的元素個數不超過 n