020 Valid Parentheses[E]

02-25

1 題目描述

Given a string containing just the characters (, ), {, }, [ and ], determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

難度：Easy

2 題目樣例

無

3 題意分析

括弧匹配，而且是最簡單的那種。

4 思路分析

遍歷字元串，同時維護一個棧，遇到左括弧入棧，遇到右括弧判定是否匹配，如果匹配棧頂出棧否則返回false，遍歷完後如果棧為空返回true否則返回false。

class Solution {public: bool isValid(string s) { stack<char> st; char tp; for(auto &c : s){ switch(c){ case (: case [: case {: st.push(c); break; case ): case ]: case }: if(st.empty()) return false; tp = st.top(); if((tp == ( && c == )) || (tp == [ && c == ]) || (tp == { && c == })) st.pop(); else return false; default: continue; } } if(st.empty()) return true; else return false; }};

整體時間複雜度可以用攤還分析出來是 $O(n)$ ，空間複雜度也是 $O(n)$ 。

5 後記

名副其實的Easy題。