大家好呀，我是帅蛋。
今天来判断括号是否有效，常见题。
不知道说啥，开整吧。
LeetCode 20：有效的括号
题意
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
示例
输入：s = "()[]{}"
输出：true
输入：s = "([)]"
输出：false
提示
有效字符串需满足：
- 左括号必须用相同类型右括号闭合
- 左括号必须以正确顺序闭合
1 <= s.length <= 10^4
s 仅由括号 () [] {} 组成
题目解析
括号匹配是使用栈解决的经典问题，难度简单。
还不太会的臭宝看下面链接，本蛋写的：
看会了栈，这道题基本就会了大半，剩下小半就是动动小脑袋瓜，稍微思考。
这题就是维护一个栈，碰到左括号就入栈，碰到右括号，取出栈顶元素，判断栈顶元素和右括号是否匹配。
如果不匹配，返回 false，如果匹配则重复上述步骤，直到遍历完字符串。
需要注意的是，有两种特殊情况也是返回 false：
- 遍历完整个字符串，栈不为空，说明多了左括号。
- 碰到右括号，但此时栈为空，说明多了右括号。
抛除上面的情况，其余的都返回 true。
图解
假设 s = "()[]{}"
首先初始化。
# 初始化 stack = [] pairs = { ')': '(', ']': '[', '}': '{' }
根据“题目解析”中说的，碰到左括号入栈，所以第 1 步，"(" 入栈
for i in s: # 如果是左括号，压入栈 if i not in pairs: stack.append(i)
接下来碰到右括号 ")"，取出栈顶元素 "("，判断栈顶元素是否和当前右括号配对，结果发现配对。
既然匹配，那就继续进行下 1 步，接下来碰到左括号 "["，入栈。
接下来碰到右括号 "]"，取出栈顶元素 "["，判断栈顶元素是否和当前右括号配对，结果发现配对。
既然又匹配，那就继续进行下 1 步，接下来碰到左括号 "{"，入栈。
接下来碰到右括号 "}"，取出栈顶元素 "{"，判断栈顶元素是否和当前右括号配对，结果发现配对。
此时字符串全部遍历完，同时栈也为空，字符串 s 有效，返回 true。
return not stack
再来假设 s = "([)]"
前两个元素都是左括号，所以直接入栈。
啥接下来碰到右括号 ")"，取出栈顶元素 "["，栈顶元素与右括号不匹配，返回 false。
# 在遍历过程中，碰到空栈或者括号不匹配，返回 False。 elif not stack or pairs[i] != stack.pop(): return False
每个元素的进栈或出栈的操作都是 O(1)，最坏情况下，每个元素都会进且仅进栈 1 次，所以时间复杂度为 O(1) * n = O(n)。
同理，最坏情况下，是所有的元素都入栈，所以空间复杂度也为 O(n)。
代码实现
Python 代码实现
class Solution: def isValid(self, s: str) -> bool: # 字符串有奇数个元素，不匹配 if len(s) % 2 == 1: return False # 初始化栈 stack = [] pairs = { ')': '(', ']': '[', '}': '{' } for i in s: # 如果是左括号，压入栈 if i not in pairs: stack.append(i) # 在遍历过程中，碰到空栈或者括号不匹配，返回 False。 elif not stack or pairs[i] != stack.pop(): return False # 全部遍历完，如果栈为空，返回 True，栈不为空，返回 False return not stack
Java 代码实现
class Solution { public boolean isValid(String s) { Deque<Character> deque = new LinkedList<>(); char ch; for (int i = 0; i < s.length(); i++) { ch = s.charAt(i); //碰到左括号，就把相应的右括号入栈 if (ch == '(') { deque.push(')'); }else if (ch == '{') { deque.push('}'); }else if (ch == '[') { deque.push(']'); } else if (deque.isEmpty() || deque.peek() != ch) { return false; }else {//如果是右括号判断是否和栈顶元素匹配 deque.pop(); } } //最后判断栈中元素是否匹配 return deque.isEmpty(); } }
图解有效的括号到这里就结束啦。
栈的实战第一道题，题目比较简单，写写画画仔细思考一定没问题哒。
有问题，扔到留言区。
看到这都是真爱，记得点赞在看么么哒呀。
我是帅蛋，我们下次见！
