- 一个字符串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
}功能测试
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功能基本实现。
单元测试
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)
})
})性能分析
- 时间复杂度O(n)
- 空间复杂度O(n)
对于时间复杂度：关于includes这个API来说，它的时间复杂度是O(n), 但是在这里只用了3个固定的字符来使用这个API，计算量可以算为常量级别。
对于空间复杂度：这里新建了一个数组，它的长度大小和字符串里面包含的左括号成正比，所以在这里它的空间复杂度是O(n)数量级。
