题目
- 一个字符串 s 可能包含 { } ( ) [ ] 三种括号
- 判断 s 是否是括号匹配的
- 如(a{b}c) 匹配，而 {a(b 或 {a(b}c) 不匹配
栈
- 先进后出
- API： push pop length
- 相关的：队列、堆
栈和数组的关系或区别
栈是一种逻辑结构，理论模型，不管如何实现，都不受任何语言的限制。
数组是一个物理结构，真实的功能实现，受限于编程语言。
解题思路
- 遇到左括号 ( [ { 就压入栈
- 遇到右括号 } ] ) 就判断栈顶，匹配则出栈
- 最后判断 length 是否为 0
时间复杂度 O(n) 空间复杂度 O(n)
match-bracket.ts
// 括号匹配// 判断左右括号是否匹配
function isMatch(left: string, right: string) {if(left === '{' && right === '}') return trueif(left === '[' && right === ']') return trueif(left === '(' && right === ')') return true
}export function matchbracket(str: string): boolean {const length = str.lengthif (length === 0) return trueconst stack = []// includes 固定的长度和数据量无关const leftSymbols = '{[('const rightSymbols = '}])'for (let i = 0; i < length; i++) {const s = str[i]if(leftSymbols.includes(s)) {// 左括号，压栈stack.push(s)} else if (rightSymbols.includes(s)) {const top = stack.[stack.length - 1]if(isMatch(top, s)) {stack.pop()} else {return false}}}return stack.length === 0
}match-bracket.test.ts
import { matchBracket } from './match-bracket'describe('括号匹配', () => {it('正常情况', () => {const str = '{a(b[c]d)e}f'const res = matchBracket(str)expect(res).toBe(true)})it('不匹配', () => {const str = '{a(b[(c]d)e}f'const res = matchBracket(str)expect(res).toBe(true)})it('顺序不一致', () => {const str = '{a(b[(c]d}e)f'const res = matchBracket(str)expect(res).toBe(true)})it('空字符串', () => {const str = ''const res = matchBracket(str)expect(res).toBe(true)})
})
