3、判断一个字符串的括号是否成对匹配

判断一个字符串的括号是否成对匹配

• 一个字符串str可能包含 {} （）[] 三种括号
• 判断 str 是否是括号成对匹配
• 如 （a{b}c）匹配，而 {a（b 或者 {a（b}c）就不匹配

了解栈

• 先进后出
• API：push pop length
• 相关的：队列，堆

逻辑结构 VS 物理结构

• 栈 VS 数组
• 栈：逻辑结构。理论模型，不管如何实现，不受任何语言的限制
• 数组：物理结构。真实的功能实现，受限于编程语言

数组可以实现栈，栈是一个抽象的模型，栈实现不了数组

解题思路

• 遇到左括号 {([ 就压栈（入栈）
• 遇到右括号})] 就判断栈顶，匹配则出栈，不匹配这直接返回false
• 最后判断length是否为0，是则返回true，反之false

代码实现功能

function matchBracket (str: string): boolean {
  const len = str.length
  if (len === 0) return true;

  const leftBracket = '({['
  const rightBracket = ')}]'
  const stack = []

  for ( let i = 0; i < len; i++) {
    const s = str[i]
    if (leftBracket.includes(s)) {
      // 左括号压栈
      stack.push(s)
    } else if (rightBracket.includes(s)) {
      // 获取左括号的栈顶元素
      const top = stack[stack.length -1]
      if (
        (top === '(' && s === ')') ||
        (top === '{' && s === '}') || 
        (top === '[' && s === ']')
      ) {
        // 右括号出栈
        stack.pop()
      } else {
        // 不成对匹配，匹配失败
        return false;
      }
    }
  }
  return stack.length === 0
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

功能测试

const res1 = matchBracket('(a{b}c)')
const res2 = matchBracket('(a{b)c]')
const res3 = matchBracket('(a{b')
const res4 = matchBracket('')
console.log(res1) // true
console.log(res2) // false
console.log(res3) // true
console.log(res4) // true
1
2
3
4
5
6
7
8

功能基本实现。

单元测试

describe('括号匹配', () => {
    it('正常情况', () => {
        const str = '(a{b}c)'
        const res = matchBracket(str)
        expect(res).toBe(true)
    })
    
    it('不匹配情况', () => {
        const str = '(a{b)c]'
        const res = matchBracket(str)
        expect(res).toBe(true)
    })
    
    it('字符串为空的情况', () => {
        const str = ''
        const res = matchBracket(str)
        expect(res).toBe(true)
    })
})
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

性能分析

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

对于时间复杂度：关于includes这个API来说，它的时间复杂度是O(n), 但是在这里只用了3个固定的字符来使用这个API，计算量可以算为常量级别。

对于空间复杂度：这里新建了一个数组，它的长度大小和字符串里面包含的左括号成正比，所以在这里它的空间复杂度是O(n)数量级。