有效的括号 -20

栈问题

描述

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

有效字符串需满足：

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

示例 1:

输入: "()"
输出: true

复制代码示例 2:

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

复制代码示例 3:

输入: "(]"
输出: false

复制代码示例 4:

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

复制代码示例 5:

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

TL;DR

简单来说，就是从左到右对括号字符串进行遍历。

在遍历过程中，如果遇到右括号，那么就与对应的左括号抵消掉。

代码

function isValidBracket (s: string) {
  // 首先把空格去掉
  s = s.replaceAll(' ', '')
  const n = s.length
  // 如果是奇数个括号，肯定不符合要求
  if(n % 2 === 1) {
    return false
  }
  // 右括号映射
  const rightBracketMap = new Map([
    ['}', '{'],
    [')', '('],
    [']', '[']
  ])
  // 存储左括号的数组
  const leftBracketArr = [] as string[]
  // 对括号字符串进行遍历
  // 字符串能使用 for...of 遍历，因为字符串有内置迭代器
  // 从左到右一次遍历
  for(const char of s) {
    // 如果是有效括号字符串，一开始不会遇到右括号
    if(rightBracketMap.has(char)) {
      if(leftBracketArr[leftBracketArr.length - 1] === rightBracketMap.get(char)) {
        // 如果左括号与右括号匹配，就把左括号抵消掉
        leftBracketArr.pop()
      } else {
        // 否则没有匹配的，不符要求，返回 false
        return false
      }
    } else {
      leftBracketArr.push(char)
    }
  }
  // 如果最后的左括号数组还留有为抵消完的左括号，那么也不符合题目要求！
  return !leftBracketArr.length
}

// in-source test suites
if (import.meta.vitest) {
  const { it, expect } = import.meta.vitest
  
  it('test', () => {
    expect(isValidBracket('{()}')).toBe(true)
    expect(isValidBracket('((')).toBe(false)
    expect(isValidBracket('{} {{{}}} ({})   (){{{}}}')).toBe(true)
  })
}

LeetCode 链接

https://leetcode-cn.com/problems/valid-parentheses

有效的括号 -20 ​

描述 ​

TL;DR ​

代码 ​

LeetCode 链接 ​

有效的括号 -20

描述

TL;DR

代码

LeetCode 链接