[数据结构与算法]算法-考察栈数据结构

励志分享：行动是治愈恐惧的良药，而犹豫拖延将不断滋养恐惧。

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

1. 左括号必须用相同类型的右括号闭合。

2. 左括号必须以正确的顺序闭合。

   示例：

   示例 1：
   输入：s = "()"
   输出：true
   
   示例 2：
   输入：s = "()[]{}"
   输出：true
   
   示例 3：
   输入：s = "(]"
   输出：false
   
   示例 4：
   输入：s = "([)]"
   输出：false
   
   示例 5：
   输入：s = "{[]}"
   输出：true
   
   

   根据题目推断出：

   1. 字符串s的长度一定是偶数，一对对匹配；
   2. 右括号前面一定跟着左括号，才对称；
   3. 右括号前面如果不是左括号，一定不是有效的括号。

   解法一：暴力消除法

   既然括号是成对出现的，不如把他们挨个消除掉，如果最后时空字符串，那么就是有效字符了。

   举个例子：

   输入：s = "{[()]}"
   
   第一步：可以消除()这一对，结果s还剩{[]}
   
   第二步: 可以消除[]这一对，结果s还剩{}
   
   第三步: 可以消除{}这一对，结果s还剩'' 所以符合题意返回true
   
   
   

   代码实现：

   function isValid(str){
       while(true){   //while循环一开始不判断条件直接执行，所以while内的代码至少执行一次
           let len = str.length;//进入循环时str的长度
           str = str.replace('{}','').replace('()','').replace('[]','')
           let newLen = str.length
           //str的长度有两种情况
        	//1.str匹配完了，变成了空字符串
           //2.str无法继续匹配，导致其长度和此次的长度一样，比如某次匹配中str为({],长度是3，匹配之后还是3，说明泵继续匹配了，结果就是false
           if(newLen ===len){//如果替换之前的长度跟替换之后的长度一样，就是不能匹配了
               return len===0   //此时的return两个作用 1.终止while循环 2.返回函数结果，即是否为有效字符
           }
       }
   }
   
   
   

   解法二：栈解题法

   思路：根据对称性。而栈（后入先出），入栈abc,出栈cab，所以可以从栈的角度解析：

输入s = '{[()]}'
第一步：读取字符 '{',属于左括号，入栈；
第二步：读取字符 '[',属于左括号，入栈；
第三步：读取字符 '(',属于左括号，入栈；此时栈里字符从底部到顶部 '{[('

第四步：读取字符 ')',属于右括号，尝试与栈顶元素匹配，刚好栈顶字符 '(',匹配，然后将'(' 出栈，可以想象着它的小伙伴去救他啦！
第五步：读取字符 ']',属于右括号，此时栈内元素从栈底到栈顶为'{[',尝试与栈顶字符匹配，刚好与'['匹配，将'['出栈
第六步：同第4、5步，最后栈内只剩 '',则说明s符合有效字符的定义，返回true

代码实现：

function isVaild(str) {
        if (!str) {
            return true;//空字符也属于有效字符
        }
        const groupObj = {  //key:左括号  value:右括号
            '{': '}',
            '[': ']',
            '(': ')'
        }
        let stack = []//栈
        for(let chart of str){
        	if(chart in groupObj){//左括号
        		stack.push(chart)
        	}else{//右括号
        		if(!stack.length||chart!=grounpObj[stack.pop()]){
	       			return false
	            }
        }
        // 如果最后stack 里没有元素了， 就一定是匹配的
        return !stack.length
    }
let str = '{[()]}'
isVaild(str)

两种方法对比：

栈方法 ： 耗时少、消耗内存也少
暴力消除法： 编码简单

https://juejin.cn/post/7067315820937871373