[LeetCode] 20. Valid Parentheses

20. Valid Parentheses

• Hardness: \(\color{green}\textsf{Easy}\)
• Ralated Topics: String、Stack

一、題目

Given a string s containing just the characters (, ), {, }, [ and ], determine if the input string is valid.
An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

Example 1:

• Input: s = ”()”
• Output: true

Example 2:

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

Example 3:

• Input: s = ”(]”
• Output: false

Constraints:

• 1 <= s.length <= 10^4
• s consists of parentheses only ()[]{}.

二、分析

• 利用 stack 來解題。
• 遇到左括號時，將括號推至 stack 上，
  遇到右括號時，確認 stack 頂端是否為對應的括號，否則回傳 false。
• 最後所有的括號都有配對到時，stack 必須為空。

三、解題

1. Stack

• Time complexity: \(O(n)\)
• Space complexity: \(O(1)\)

unordered_map<char,char> map = {{'[',']'}, {'(',')'}, {'{','}'}};
bool isValid(string s) {
    stack<char> st;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '[' || s[i] == '(' || s[i] == '{') {    // 左括號推到 stack 上
            st.push(s[i]);
        } else {
            if (st.empty() || s[i] != map[st.top()]) return false;  // 右括號檢查 stack 是否有配對到
            st.pop();
        }
    }
    return st.empty();  // 檢查 stack 是否為空
}

回目錄 Catalog