# 0020. 有效的括号

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

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

### 题目描述

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true
示例 2:

输入: "()[]{}"
输出: true
示例 3:

输入: "(]"
输出: false
示例 4:

输入: "([)]"
输出: false
示例 5:

输入: "{[]}"
输出: true

```

### 前置知识

* [栈](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/thinkings/basic-data-structure)

### 公司

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

### 栈

#### 思路

关于这道题的思路，邓俊辉讲的非常好，没有看过的同学可以看一下，[视频地址](http://www.xuetangx.com/courses/course-v1:TsinghuaX+30240184+sp/courseware/ad1a23c053df4501a3facd66ef6ccfa9/8d6f450e7f7a445098ae1d507fda80f6/)。

使用栈，遍历输入字符串

如果当前字符为左半边括号时，则将其压入栈中

如果遇到右半边括号时，分类讨论：

1）如栈不为空且为对应的左半边括号，则取出栈顶元素，继续循环

2）若此时栈为空，则直接返回 false

3）若不为对应的左半边括号，反之返回 false

![20.validParentheses](https://p.ipic.vip/4j38xn.gif)

（图片来自： <https://github.com/MisterBooo/LeetCodeAnimation>)

值得注意的是，如果题目要求只有一种括号，那么我们其实可以使用更简洁，更省内存的方式 - 计数器来进行求解，而不必要使用栈。 而之所以多种括号不可以使用计数器在 $O(1)$ 空间做到是因为类似这种用例会无法处理 "(\[)]"。

#### 关键点解析

1. 栈的基本特点和操作
2. 可以用数组来模拟栈

比如 入： push 出：pop 就是栈。 入： push 出 shift 就是队列。 但是这种算法实现的队列在头部删除元素的时候时间复杂度比较高，具体大家可以参考一下[双端队列 deque](https://zh.wikipedia.org/wiki/%E5%8F%8C%E7%AB%AF%E9%98%9F%E5%88%97)。

#### 代码

代码支持：JS，Python，Java，C++

Javascript Code:

```js
/**
 * @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:

```py
    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:

```java
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:

```cpp
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)$。

具体参考： [No stack O(1) space complexity O(n) time complexity solution in C++](https://leetcode.com/problems/valid-parentheses/discuss/9478/No-stack-O\(1\)-space-complexity-O\(n\)-time-complexity-solution-in-C++/244061)

#### 代码

代码支持：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:

```py
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:

```js
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;
};
```

**复杂度分析**

* 时间复杂度：取决于正则引擎的实现
* 空间复杂度：取决于正则引擎的实现

### 相关题目

* [32. 最长有效括号](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/32.longest-valid-parentheses)

### 扩展

* 如果让你检查 XML 标签是否闭合如何检查， 更进一步如果要你实现一个简单的 XML 的解析器，应该怎么实现？
* 事实上，这类问题还可以进一步扩展，我们可以去解析类似 HTML 等标记语法， 比如 `<p></p> <body></body>`

更多题解可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://p.ipic.vip/zl5m7q.jpg)