Skip to content

Latest commit

 

History

History
225 lines (162 loc) · 4.98 KB

20.valid-parentheses.md

File metadata and controls

225 lines (162 loc) · 4.98 KB

题目地址

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

题目描述

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true
Example 2:

Input: "()[]{}"
Output: true
Example 3:

Input: "(]"
Output: false
Example 4:

Input: "([)]"
Output: false
Example 5:

Input: "{[]}"
Output: true

前置知识

  • 栈

栈

思路

关于这道题的思路，邓俊辉讲的非常好，没有看过的同学可以看一下，视频地址。

使用栈，遍历输入字符串

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

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

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

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

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

20.validParentheses

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

值得注意的是，如果题目要求只有一种括号，那么我们其实可以使用更简洁，更省内存的方式 - 计数器来进行求解，而 不必要使用栈。

事实上，这类问题还可以进一步扩展，我们可以去解析类似 HTML 等标记语法， 比如

关键点解析

  1. 栈的基本特点和操作
  2. 如果你用的是 JS 没有现成的栈，可以用数组来模拟 入： push 出：pop

入： push 出 shift 就是队列

代码

代码支持：JS，Python

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

O(1) 空间

思路

基本思路是修改参数，将参数作为我们的栈。 随着我们不断遍历， s 慢慢变成了一个栈。

因此 Python，Java，JS 等字符串不可变的语言无法使用此方法达到 $O(1)$。

具体参考： No stack O(1) space complexity O(n) time complexity solution in C++

代码

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

正则匹配

思路

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

代码

代码支持：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 的解析器，应该怎么实现？