LeetCode-20.有效的括号

题目详解

相关链接

• 代码随想录

思路

• 遍历字符串
  • 遇到左括号->入栈;
  • 遇到右括号->出栈 并判断出栈元素是否与当前的遍历到的右括号成对，不成对则终止

看完代码随想录之后的想法

• 使用字典来简化判断逻辑

实现过程中遇到的困难

代码

TypeScript

function isValid(s: string): boolean {
  if (s.length % 2 !== 0) return false
  const stack: string[] = []
  const map = {
    '(': ')',
    '[': ']',
    '{': '}'
  }
  for (const c of s) {
    if (c in map) stack.push(c)
    else if (map[stack.pop()] !== c) return false
  }
  return !stack.length
}

时间复杂度：O(n)
空间复杂度：O(n)

收获

• 数据结构与算法的应用往往隐藏在我们看不到的地方