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