LeetCode20 有效的括号

前言

题目： 20. 有效的括号
文档： 代码随想录——有效的括号
编程语言： C++
解题状态： 自己的做法空间复杂度过高

思路

括号匹配是使用栈解决的经典问题。本题技巧性比较强，思考的时候要与栈的使用相对照，这样容易得到思路。

代码

class Solution {
public:bool isValid(string s) {if (s.size() % 2 != 0) return false;stack<char> st;for (int i = 0; i < s.size(); i++) {if (s[i] == '(') {st.push(')');} else if (s[i] == '[') {st.push(']');} else if (s[i] == '{') {st.push('}');} else if (st.empty() || st.top() != s[i]) {return false;} else {st.pop();}}return st.empty();}
};

• 时间复杂度： $O(n)$
• 空间复杂度： $O(n)$