20.有效的括号.md

20.有效的括号

/*
 * @lc app=leetcode.cn id=20 lang=typescript
 *
 * [20] 有效的括号
 */

// @lc code=start
function isValid(s: string): boolean {}
// @lc code=end

解法 1: 用栈(Stack)

• 时间复杂度:
• 空间复杂度:

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

function isValid(s: string): boolean {
  if (s.length % 2 !== 0) return false

  let minStack = []
  for (const c of s) {
    if (c === '(') {
      minStack.push(')')
    } else if (c === '[') {
      minStack.push(']')
    } else if (c === '{') {
      minStack.push('}')
    } else if (minStack.pop() !== c) {
      return false
    }
  }
  return minStack.length === 0
}

解法 2: 替换法

• 时间复杂度:
• 空间复杂度:

function isValid(s: string): boolean {
  if (s.length % 2 !== 0) return false

  let length = 0
  let regex = /(\(\))|(\[\])|(\{\})/g
  while (s.length !== length) {
    length = s.length
    s = s.replace(regex, '')
  }
  if (s.length === 0) {
    return true
  } else {
    return false
  }
}

Case

test.each([
  { input: { s: '()' }, output: true },
  { input: { s: '()[]{}' }, output: true },
  { input: { s: '(]' }, output: false },
  { input: { s: '([)]' }, output: false },
  { input: { s: '{[]}' }, output: true },
  { input: { s: '[' }, output: false },
])('input: s = $input.s', ({ input: { s }, output }) => {
  expect(isValid(s)).toBe(output)
})