1. 题目描述

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

有效字符串需满足：

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

示例 1:

  1. 输入: "()"
  2. 输出: true

示例 2:

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

示例 3:

  1. 输入: "(]"
  2. 输出: false

示例 4:

  1. 输入: "([)]"
  2. 输出: false

示例 5:

  1. 输入: "{[]}"
  2. 输出: true

2. 解题思路

看到这种括号匹配的题目，可以使用栈来解决：

  • 首先用一个哈希表来存储三种括号的对应关系
  • 对字符串进行遍历，遇到左括号一律入栈，
  • 若不是左括号，就必须是和栈顶相匹配的右括号
  • 最后遍历完，栈中应该为空

    3. 代码实现

    1. /**
    2. * @param {string} s
    3. * @return {boolean}
    4. */
    5. var isValid = function(s) {
    6.   if(!s){
    7.       return true
    8.   }
    9.   let stack = []
    10.   let len = s.length
    11.   let brackets = {
    12.       "(": ")",
    13.       "[": "]",
    14.       "{": "}"
    15.   }
    16.   for(let i=0; i<len; i++){
    17.       let char = s[i];
    18.       if(char==="(" || char==="{" || char==="["){
    19.           stack.push(brackets[char])
    20.       }else{
    21.           if(!stack.length || stack.pop()!=char){
    22.               return false
    23.           }
    24.       }
    25.   }
    26.   return !stack.length
    27. };

    4. 提交结果

    20. 有效的括号 - 图1