有效括号

介绍

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。

示例1

输入: "()"
输出: true

示例2

输入: "()[]{}"
输出: true

示例3

输入: "(]"
输出: false

示例4

输入: "([)]"
输出: false

示例5

输入: "{[]}"
输出: true

题解

思路

判断括号的有效性可以使用「栈」这一数据结构来解决。

我们对给定的字符串 str 进行遍历，当我们遇到一个左括号时，我们会期望在后续的遍历中，有一个相同类型的右括号将其闭合。

当我们遇到一个右括号时，我们需要将一个相同类型的左括号闭合。此时，我们可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型，或者栈中并没有左括号，那么字符串 str 无效，返回 false。

在遍历结束后，如果栈中没有括号，说明我们将字符串 str 中的所有括号闭合，返回 true，否则返回 false。

注意：空字符串可被认为是有效字符串。

注意：如果字符串个数为奇数的话，那么肯定是无效字符串，直接返回false

注意：如果字符串的最后一个为左括号的话，那肯定也是无效字符串，直接返回false。反之，如果字符串的第一个为右括号的话，那肯定也是无效字符串

解法一

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    //空字符串可被认为是有效字符串。
    if(s=="") return true  
    //如果字符串个数为奇数的话，那么肯定是无效字符串，直接返回false
    if(s.length % 2 === 1) return false; 
    //如果字符串的最后一个为左括号的话，那肯定也是无效字符串，直接返回false
    if(s[s.length-1]=='(' || s[s.length-1]=='{' || s[s.length-1]=='[') return false; 
    //如果字符串的第一个为右括号的话，那肯定也是无效字符串
    if(s[0]==')' || s[0]=='}' || s[0]==']') return false; 

    const result=[] //存储左括号

    for(let i=0;i<s.length;i++){
         //左括号全部入栈
        if(s[i]=='(' || s[i]=='{' || s[i]=='[') {
            result.push(s[i]);
             continue;
        } 

        //如果是右括号，判断栈顶是否是对应的左括号，是的话弹出栈顶
        if(s[i]==')' && result[result.length-1]=='('){
            result.pop()
            continue;
        }
        if(s[i]=='}' && result[result.length-1]=='{'){
            result.pop()
            continue;
        }
        if(s[i]==']' && result[result.length-1]=='['){
            result.pop()
            continue;
        }
    }

    //处理完字符串后如果栈中还有数据说明字符串中括号没有全部匹配，反之没有数据的话说明全部匹配
   return result.length==0
};

题解二

在题解一的思路上，优化一下代码的实现，利用key/value的形式来优化速度

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    //空字符串可被认为是有效字符串。
    if(s=="") return true  
    //如果字符串个数为奇数的话，那么肯定是无效字符串，直接返回false
    if(s.length % 2 === 1) return false; 
    //如果字符串的最后一个为左括号的话，那肯定也是无效字符串，直接返回false
    if(s[s.length-1]=='(' || s[s.length-1]=='{' || s[s.length-1]=='[') return false; 
    //如果字符串的第一个为右括号的话，那肯定也是无效字符串
    if(s[0]==')' || s[0]=='}' || s[0]==']') return false; 
     let obj = {
          '{': '}',
          '(': ')',
          '[': ']'
      }
      let stack = []
      for(let i = 0; i < s.length ; i++) {
          if(obj[s[i]]) {
            stack.push(s[i]);
          } else if(s[i] !== obj[stack.pop()]){
            return false
          }
      }
      return stack.length === 0
};