20. 有效的括号
点击上方，跳转至leetcode
题目描述
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
提示：
1 <= s.length <= 104s仅由括号'()[]{}'组成
解法
方法一：栈
遍历括号字符串 \(s\)，遇到左括号时，压入当前的左括号；遇到右括号时，弹出栈顶元素(若栈为空，直接返回 false)，判断是否匹配，若不匹配，直接返回 false。
也可以选择遇到左括号时，将右括号压入栈中；遇到右括号时，弹出栈顶元素(若栈为空，直接返回 false)，判断是否是相等。若不匹配，直接返回 false。
两者的区别仅限于括号转换时机，一个是在入栈时，一个是在出栈时。
遍历结束，若栈为空，说明括号字符串有效，返回 true；否则，返回 false。
时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为括号字符串 \(s\) 的长度。
Python3
class Solution:def isValid(self, s: str) -> bool:if len(s) % 2 == 1:return Falsepairs = {")": "(","]": "[","}": "{",}stack = list()for ch in s:if ch in pairs:if not stack or stack[-1] != pairs[ch]:return Falsestack.pop()else:stack.append(ch)return not stackC++
class Solution {
public:bool isValid(string s) {int n = s.size();if (n % 2 == 1) {return false;}unordered_map<char, char> pairs = {{')', '('},{']', '['},{'}', '{'}};stack<char> stk;for (char ch: s) {if (pairs.count(ch)) {if (stk.empty() || stk.top() != pairs[ch]) {return false;}stk.pop();}else {stk.push(ch);}}return stk.empty();}
};
