【栈】20.有效的括号

[lyonyang]

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

示例 5：

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

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[chuchumeme]

方法一：找规律

思路：

• 能看出最中间的两项肯定是闭合的，可以用indexOf去判断字符串中是否存在
• 如果存在就从字符串中用splice去掉，直到没有符合的为止，最后看字符串的长度是否为0
• 注意肯定是偶数

时间复杂度：O(n) 空间复杂度 0(1)

代码

var isValid = function(s) {
    let arr = ['{}','()','[]']
    if (s.length%2 != 0) return false;
    while((s.indexOf('()')>=0 || s.indexOf('{}')>=0 || s.indexOf('[]')>=0)){
        for(var i=0;i<arr.length;i++){
        var s=s.replace(arr[i],"");
        }
    }
    if(s.length<1 || s=="()" || s=="[]" || s=="{}"){
        return true;
    }else{
        return false;
    }
};

方法二：使用栈

思路

• 创建一个新数组，从左到右遍历字符串
• 遇到左括号入栈，遇到右括号出栈
• 如果遇到右括号时，出栈的左括号并不是对应的就是false

时间复杂度：O(n) 空间复杂度 O(1)

代码

var isValid = function(s) {
    let stack = [], length = s.length;
    if(length % 2) return false;
    for(let item of s){
        switch(item){
            case "{":
            case "[":
            case "(":
                stack.push(item);
                break;
            case "}":
                if(stack.pop() !== "{") return false;
                break;
            case "]":
                if(stack.pop() !== "[") return false;
                break;
            case ")":
                if(stack.pop() !== "(") return false;
                break;
        }
    }
    return !stack.length; // 0取反是true
};

[zhangke666163]

字符串替换

思路

• 将字符串中的()、{}、[]用空替换掉
• 替换完成后，看字符串是否为空
• 注意字符串长度为奇数时，肯定不满足要求

时间复杂度O(n)，空间复杂度O(1)

代码

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) %2 == 1:
            return False
        while '()' in s or '{}' in s or '[]' in s:
            s = s.replace('()', '')
            s = s.replace('{}', '')
            s = s.replace('[]', '')
        return s == ''

[lyonyang]

思路一 - 栈

先将括号入栈 , 遇到匹配的就出栈 , 最后栈为空

注意 : k 可能大于数组长度

class Solution:
    def isValid(self, s: str) -> bool:
        _stack = []
        brackets = {'(': ')', '{': '}', '[': ']'}
        for i in s:
            if _stack:
                if brackets.get(_stack[-1], None) == i:
                    _stack.pop()
                    continue
            _stack.append(i)
        return False if _stack else True

时间复杂度：$O(N)$ , N 为数组长度

空间复杂度：$O(N)$

思路二 - 字符串替换

左括号和又括号一定是对应的 , 所以我们可以直接替换 () , {} , [] 为空字符串 , 如果结果为空字符串就说明有效

注意 : 有可能存在嵌套的括号 , 所以要循环替换

class Solution:
   def isValid(self, s: str) -> bool:
       while '()' in s or '{}' in s or '[]' in s:
           s = s.replace('()', '').replace('{}', '').replace('[]', '')
       return False if s else True

时间复杂度：$O(N)$ , N 为数组长度

空间复杂度：$O(N)$