leetcode top100挑战, 每天不鸽一道题之有效的括号(3/100)-一一网

这是我参与更文挑战的第10天，活动详情查看：更文挑战

题目描述

寻找两个正序数组的中位数

给定一个只包括 ‘(‘，’)’，'{‘，’}’，'[‘，’]’ 的字符串 s ，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。

leetcode-cn.com/problems/va…

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

复制代码

解题分析

1. 栈

这道题可以用栈的思路来解决，需要注意的以下几点：

传入的字符串中，左括号必须要有右括号闭合。
如果这个字符串是右括号，而没有左括号，那就直接返回false。
如果传入的字符串长度为奇数，那就肯定是不符合的，直接返回false。

首先遍历传入的字符串，如果是左字符串，那就推入栈中。如果是右字符串，首先判断栈中是否有数据，如果有并且和当前遍历的字符闭合，那就把栈顶的字符推出。

循环完毕后，如果栈内没有落单的括号，那就说明符合了。

假设传入的字符串s为 '{()[]{}}'

我们开始遍历字符串

第一次遍历，如果是左括号，直接推入栈。
当前遍历的数： {
栈里的数据： [] //注意这是空数组，不是括号闭合 

第二次遍历，还是左括号，继续推入                
当前遍历的数： (
栈里的数据： [ '{' ]

第三次遍历，总算来右括号了，看一下栈顶是否有可以闭合的')'，有了，那就推出栈顶 '('                
当前遍历的数： )
栈里的数据： [ '{', '(' ]

第四次遍历， 还是左括号，推进去                
当前遍历的数： [
栈里的数据： [ '{' ]

第五次遍历，来了来了他来了，拿出栈顶的匹配下，可以相亲成功，推出'['                
当前遍历的数： ]
栈里的数据： [ '{', '[' ]

第六次遍历，我都不想说了左括号特么直接推进去
当前遍历的数： {
栈里的数据： [ '{' ]
第七次遍历，有的有的，直接推出，                
当前遍历的数： }
栈里的数据： [ '{', '{' ]
最后一次遍历，符不符合？？？符合特么就退推出去                
当前遍历的数： }
栈里的数据： [ '{' ]

最后栈为 [] 所以传入的string '{()[]{}}' 符合结果！


复制代码

来人上代码！！！！！

function isValid(s: string): boolean {

   const len: number = s.length 
    //    如果是奇数，那就说明总会多出一个，立马返回false
   if(len % 2 === 1) return false 

   const map = new Map([
        [')', '('],
        [']', '['],
        ['}', '{']
   ])

   const stk: string[] = []

   for(let code of s ) {
       
       if(map.has(code)) {
        //    如果他是右括号  那就判断
        // 1. 栈里没数据，那就说明当前遍历的右括号是个没有老婆左括号的括号，那就返回false
        // 2. 如果栈里有数据，取出栈顶的左括号，看看是不是相配的，如果不是相同类型的，那就返回false
            if(!stk.length || stk[stk.length - 1] !== map.get(code)) return false
            // 如果有符合的 那就从栈中推出
            stk.pop()
       }
        //    那就说明它不是右括号 而是 ( [ {  把他推到栈里

       else {
           stk.push(code)
       }
   }

   return !stk.length
};
复制代码