Links

0020. 有效的括号

题目地址(20. 有效的括号)

https://leetcode-cn.com/problems/valid-parentheses/description

题目描述

给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true

前置知识

公司

  • 阿里
  • 百度
  • 腾讯
  • 字节
  • airbnb
  • amazon
  • bloomberg
  • facebook
  • google
  • microsoft
  • twitter
  • zenefits

思路

关于这道题的思路,邓俊辉讲的非常好,没有看过的同学可以看一下,视频地址
使用栈,遍历输入字符串
如果当前字符为左半边括号时,则将其压入栈中
如果遇到右半边括号时,分类讨论:
1)如栈不为空且为对应的左半边括号,则取出栈顶元素,继续循环
2)若此时栈为空,则直接返回 false
3)若不为对应的左半边括号,反之返回 false
20.validParentheses
(图片来自: https://github.com/MisterBooo/LeetCodeAnimation)
值得注意的是,如果题目要求只有一种括号,那么我们其实可以使用更简洁,更省内存的方式 - 计数器来进行求解,而不必要使用栈。 而之所以多种括号不可以使用计数器在 $O(1)$ 空间做到是因为类似这种用例会无法处理 "([)]"。

关键点解析

  1. 1.
    栈的基本特点和操作
  2. 2.
    可以用数组来模拟栈
比如 入: push 出:pop 就是栈。 入: push 出 shift 就是队列。 但是这种算法实现的队列在头部删除元素的时候时间复杂度比较高,具体大家可以参考一下双端队列 deque

代码

代码支持:JS,Python,Java,C++
Javascript Code:
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function (s) {
let valid = true;
const stack = [];
const mapper = {
"{": "}",
"[": "]",
"(": ")",
};
for (let i in s) {
const v = s[i];
if (["(", "[", "{"].indexOf(v) > -1) {
stack.push(v);
} else {
const peak = stack.pop();
if (v !== mapper[peak]) {
return false;
}
}
}
if (stack.length > 0) return false;
return valid;
};
Python Code:
class Solution:
def isValid(self,s):
stack = []
map = {
"{":"}",
"[":"]",
"(":")"
}
for x in s:
if x in map:
stack.append(map[x])
else:
if len(stack)!=0:
top_element = stack.pop()
if x != top_element:
return False
else:
continue
else:
return False
return len(stack) == 0
Java Code:
class Solution {
public boolean isValid(String s) {
//1.判断空字符串
if(s.isEmpty()) return true;
//2.创建辅助栈
Stack<Character> stack = new Stack<>();
//3.仅遍历一次
for(char c : s.toCharArray()){
if(c == '('){
stack.push(')');
}else if(c == '['){
stack.push(']');
}else if(c == '{'){
stack.push('}');
}else if(stack.isEmpty() || c != stack.pop()){
return false;
}
}
//4.返回
return stack.isEmpty();
}
}
C++ Code:
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();
}
};
复杂度分析
  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(N)$

O(1) 空间

思路

基本思路是修改参数,将参数作为我们的栈。 随着我们不断遍历, s 慢慢变成了一个栈。
因此 Python,Java,JS 等字符串不可变的语言无法使用此方法达到 $O(1)$。

代码

代码支持:C++
C++:
class Solution {
public:
bool isValid(string s) {
int top = -1;
for(int i =0;i<s.length();++i){
if(top<0 || !isMatch(s[top], s[i])){
++top;
s[top] = s[i];
}else{
--top;
}
}
return top == -1;
}
bool isMatch(char c1, char c2){
if(c1 == '(' && c2 == ')') return true;
if(c1 == '[' && c2 == ']') return true;
if(c1 == '{' && c2 == '}') return true;
return false;
}
};
复杂度分析
  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(1)$

正则匹配

思路

我们不断通过消除 '[]' , '()', '{}' ,最后判断剩下的是否是空串即可,就像开心消消乐一样。

代码

代码支持:Python,JavaScript
Python:
class Solution:
def isValid(self, s):
while '[]' in s or '()' in s or '{}' in s:
s = s.replace('[]','').replace('()','').replace('{}','')
return not len(s)
JavaScript:
var isValid = function (s) {
while (s.includes("[]") || s.includes("()") || s.includes("{}")) {
s = s.replace("[]", "").replace("()", "").replace("{}", "");
}
s = s.replace("[]", "").replace("()", "").replace("{}", "");
return s.length === 0;
};
复杂度分析
  • 时间复杂度:取决于正则引擎的实现
  • 空间复杂度:取决于正则引擎的实现

相关题目

扩展

  • 如果让你检查 XML 标签是否闭合如何检查, 更进一步如果要你实现一个简单的 XML 的解析器,应该怎么实现?
  • 事实上,这类问题还可以进一步扩展,我们可以去解析类似 HTML 等标记语法, 比如 <p></p> <body></body>
更多题解可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。