題號20：Invalid?Parentheses

Given a string 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.

Note that an empty string is?also considered valid.

Example 1:

Input: "()"
Output: true

Example 2:

Input: "(]"
Output: false

算法

1. 初始化棧 S。
2. 一次處理表達式的每個括號。
3. 如果遇到開括號，我們只需將其推到棧上即可。這意味著我們將稍后處理它，讓我們簡單地轉到前面的?子表達式。
4. 如果我們遇到一個閉括號，那么我們檢查棧頂的元素。如果棧頂的元素是一個相同類型的左括號，那么我們將它從棧中彈出并繼續處理。否則，這意味著表達式無效。
5. 如果到最后我們剩下的棧中仍然有元素，那么這意味著表達式無效。

復雜度分析

• 時間復雜度：O(n)，因為我們一次只遍歷給定的字符串中的一個字符并在棧上進行?O(1)?的推入和彈出操作。
• 空間復雜度：O(n)，當我們將所有的開括號都推到棧上時以及在最糟糕的情況下，我們最終要把所有括號推到棧上。例如?((((((((((。

static const auto _ = []()
{ios::sync_with_stdio(false);cin.tie(nullptr);return nullptr;
}();class Solution {
public:bool isValid(string s) {stack<char> stack;for (int i = 0; i < s.length(); i++){char tmp = s[i];if (tmp == '(' || tmp == '[' || tmp == '{')stack.push(tmp);else{if (stack.empty())return false;char topChar = stack.top();if (topChar == '(' && tmp != ')')return false;if (topChar == '{' && tmp != '}')return false;if (topChar == '[' && tmp != ']')return false;stack.pop();}}return stack.empty();}
};

?