栈🐑

有效的括号

题目描述：给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。

链接：https://leetcode-cn.com/problems/valid-parentheses/

解法：

• 方法一：暴力法

  • 思路：找到最内层的括号对，消去，重复此过程，若存在无法消去的字符则说明字符串无效(优化点：如果字符串个数不为偶数，直接判断false)
  • 复杂度分析:
    • 时间复杂度:O(2^n)
  • 代码

    var isValid = function(s) {
    if(s.length%2!==0) return false
    while(s.length){
       let temp=s
       s=s.replace(/(\(\))|(\[\])|(\{\})/g,'')
       if(s===temp) return false
    }
    return true
    };

• 方法二：栈

  • 思路：
    • 对于左括号来说，没办法判断是否有效，压入栈中存着（push）
    • 对于右括号来说，不能独立存在，直接来个右括号肯定不合法，需要去查看堆栈的栈底是否有和它相匹配的括号（peek），如果匹配的话，需要把栈底元素推出(pop)
    • 全部判断完之后，堆栈本身应该为空
    • 注意：由于后遇到的左括号要先闭合，因此我们可以将这个左括号放入栈顶。
    • 当我们遇到一个右括号时，我们需要将一个相同类型的左括号闭合。此时，我们可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型，或者栈中并没有左括号，那么字符串无效
  • 复杂符分析：
    • 时间复杂度:O(n)：每一个元素进栈和出栈的操作时间复杂度为O(1)，每个元素有且进入这个栈一次(n)，所以时间复杂度为O(1)*n=O(n)
    • 空间复杂度：O(n)
  • 代码

    var isValid = function(s) {
    if(s.length%2!==0) return false
    const hashMap=new Map([[')','('],[']','['],['}','{']])
    const stack=[]
    for(let item of s){
     if(hashMap.has(item)){
     if(!stack.length || stack[stack.length-1]!==hashMap.get(item)){
         return false
     }
       stack.pop()
    }else{
       stack.push(item)
    }
    }
    return stack.length===0
    }