leetcode-栈-[20] 有效的括号

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

有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例

  1. 示例 1：
  2. 输入：s = "()"
  3. 输出：true
  4. 示例 2：
  5. 输入：s = "()[]{}"
  6. 输出：true
  7. 示例 3：
  8. 输入：s = "(]"
  9. 输出：false
  10. 示例 4：
  11. 输入：s = "([)]"
  12. 输出：false
  13. 示例 5：
  14. 输入：s = "{[]}"
  15. 输出：true

提示：

  • 1 <= s.length <= 104
  • s 仅由括号 ‘()[]{}’ 组成

解题思路

利用栈的先进后出规则

  1. 申明一个数组缓存符号状态
  2. 对字符串进行循环
  3. 出现左括号进行入栈操作
  4. 出现右括号进行出栈操作,拿到栈顶元素进行匹配,不匹配返回false,匹配继续进行循环
  5. 循环结束最后判断缓存数组是否有值,有值说明符号不是成对存在的返回false

    说明:

    1. const len = s.length; 可以提高性能减少计算次数, 2.if (len % 2) return false;判断字符串是否为偶数项,减少不必要的计算
  1. // 题解一 常规解题思路,便于理解
  2. /**
  3.  * @param {string} s
  4.  * @return {boolean}
  5.  */
  6. var isValid = function (s) {
  7.   let arr = [];
  8.   const len = s.length;
  9.   if (len % 2) return false;
  10.   for (var i = 0; i < len; i++) {
  11.     switch (s[i]) {
  12.       case '(':
  13.       case '[':
  14.       case '{':
  15.         arr.push(s[i]);
  16.         break;
  17.       case ')':
  18.         if (arr.pop() !== '(') return false;
  19.         break;
  20.       case ']':
  21.         if (arr.pop() !== '[') return false;
  22.         break;
  23.       case '}':
  24.         if (arr.pop() !== '{') return false;
  25.         break;
  26.     }
  27.   }
  28.   return !arr.length;
  29. };
  1. // 题解二 使用Map键值对存储,优化代码逻辑
  2. /**
  3.  * @param {string} s
  4.  * @return {boolean}
  5.  */
  6. var isValid = function (s) {
  7.   let arr = [];
  8.   let len = s.length;
  9.   const map = new Map();
  10.   map.set('(', ')');
  11.   map.set('[', ']');
  12.   map.set('{', '}');
  13.   if (len % 2) return false;
  14.   for (var i = 0; i < len; i++) {
  15.     if (map.has(s[i])) {
  16.       arr.push(s[i]);
  17.     } else {
  18.       if (!arr.length) {
  19.         return false;
  20.       }
  21.       if (map.get(arr.pop()) !== s[i]) {
  22.         return false;
  23.       }
  24.     }
  25.   }
  26.   return !arr.length;
  27. };