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

有效字符串需满足：

  • 左括号必须用相同类型的右括号闭合。
  • 左括号必须以正确的顺序闭合。
  • 每个右括号都有一个对应的相同类型的左括号。

思路

  1. 建立一个栈
  2. 遍历字符串，当前字符为左括号时进栈
  3. 当前字符为右括号时，要求栈顶元素必须是其配套的左括号并出栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var isValid = function (s) {
  const mapper = {
    ')': '(',
    ']': '[',
    '}': '{',
  }
  const stack = []
  for (const char of s) {
    if (!mapper[char]) {
      stack.push(char)
      continue
    }
    if (stack.length === 0 || stack.pop() !== mapper[char]) {
      return false
    }
  }
  return stack.length === 0
}