题目 一个字符串内部可能包含 `{ }` `( )` `[ ]` 三种括号,判断该字符串是否是括号匹配的。 如 `(a{b}c)` 就是匹配的, `{a(b` 和 `{a(b}c)` 就是不匹配的。
/* 分析 - 遇到左括号 `{ ( [` 则压栈 - 遇到右括号 `} ) ]` 则判断栈顶,相同的则出栈 - 最后判断栈 length 是否为 0 */
实现
// 判断左右括号匹配 function isMatch(left:string, right:string):boolean { if (left === '{' && right === '}') { return true } if (left === '[' && right === ']') { return true } if (left === '(' && right === ')') { return true } return false } export function matchBracket(str:string):boolean { const len = str.length if (len === 0) { return false } const stack = []; const leftSymbols = '{[('; // 固定字符串 const rightSymbols = '}])'; for (let i = 0; i < len; i++) { // 时间复杂度 O(n) const s = str[i]; if (leftSymbols.includes(s)) { // 左括号 压栈 stack.push(s) } if (rightSymbols.includes(s)) { // 右括号,判断栈顶(是否出栈),栈顶为最后一个元素 const top = stack[stack.length -1] if (isMatch(top, s)) { stack.pop() } else { return false } } } return stack.length === 0 } // 时间复杂度 O(n) // 功能测试 const str = '{a(b[c]d)e}f'; const str1 = '{a(]b[c]d)e}]f'; console.log('str',matchBracket(str)) console.log('str1',matchBracket(str1))
单测
// Jest import {rotate1, rotate2} from '../把一个数组旋转看k步' describe('数组旋转',()=>{ it('正常情况', ()=> { const arr = [1,2,3,4,5,6,7] const k = 3 const res = rotate1(arr, k) // const res = rotate2(arr, k) expect(res).toEqual([5,6,7,1,2,3,4]) // 断言 }) it('数组为空', ()=> { const res = rotate1([], 3) expect(res).toEqual([]) }) it('k是负值', ()=> { const arr = [1,2,3,4,5,6,7] const k = -3 const res = rotate1(arr, k) expect(res).toEqual([5,6,7,1,2,3,4]) }) it('k是0', ()=> { const arr = [1,2,3,4,5,6,7] const k = 0 const res = rotate1(arr, k) expect(res).toEqual(arr) }) it('k不是数字', ()=> { const arr = [1,2,3,4,5,6,7] const k = 'abc' // @ts-ignore // 报错注释 const res = rotate1(arr, k) expect(res).toEqual(arr) }) })