当前位置：首页 > news >正文

LeetCode 20.有效的括号

news 2024/9/23 15:42:32

题目描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"输出：true

示例 2：

输入：s = "()[]{}"输出：true

示例 3：

输入：s = "(]"输出：false

示例 4：

输入：s = "([])"输出：true

提示：

1 <= s.length <= 10^4
s 仅由括号 '()[]{}' 组成

思路

本题属于对称匹配类题目，共存在3种不匹配的情况：1.字符串里左方向的括号多余了，所以不匹配；2.括号没有多余，但是括号的类型没有匹配上；3.字符串里右方向的括号多余了，所以不匹配。

笔者的思路是使用栈来解决，在遍历字符串的过程中，让字符串中的左括号入栈，当遇到右括号的时候会与栈顶的符号进行比对，比对成功则删除栈顶元素，否则令其入栈。也就是说如果遇到了上面三种不匹配的情况，都会在栈中留下冗余而无法弹出。那么只需要查看最后栈是否为空就能知道结果，如果栈是空的，就说明全都匹配了。

本题有另一种更好的写法，那就是在匹配左括号的时候，右括号先入栈，此时只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈的代码实现要简单。

代码

C++版：

class Solution {
public:bool isValid(string s) {if (s.size() % 2 != 0) return false; // 如果s的长度为奇数，一定不符合要求// 使用栈stack<char> st;for(int i=0;i<s.size();i++){if(st.size()>0 && st.top()=='(' && s[i]==')'){st.pop();}else if(st.size()>0 && st.top()=='[' && s[i]==']'){st.pop();}else if(st.size()>0 && st.top()=='{' && s[i]=='}'){st.pop();}else{st.push(s[i]);}}return st.empty();}
};

Python版：

class Solution:def isValid(self, s: str) -> bool:stack = []# 另一种写法，右括号先入栈for item in s:if item == '(':stack.append(')')elif item == '[':stack.append(']')elif item == '{':stack.append('}')elif not stack or stack[-1] != item: # 发现栈里没有要匹配的字符return Falseelse:stack.pop()return True if not stack else False