【数据结构与算法】(4):判断字符串是否括号匹配


字数:399 阅读时长:1分钟 阅读:85

使用 stack)实现 判断字符串是否括号匹配 的算法。

数据结构与算法 · 括号匹配

一、问题描述

给你一个字符串,其中包含这三种类型的 ()[]{} 的括号。请你检验这个字符串是否为有效字符串,如果是有效字符串返回 true 。

示例 1:

  • 输入:s = “{(2[a]4)}”
  • 输出:true

示例 2:

  • 输入:s = “((324[bcd]{231}))”
  • 输出:true

示例 3:

  • 输入:s = “(({[[()34)]]}))”
  • 输出:false

二、代码演示

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
32
33
34
function isMatch(left: string, right: string): boolean {
if (left==='{' && right==='}') return true;
if (left==='[' && right===']') return true;
if (left==='(' && right===')') return true;
return false;
}

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

const stack:string[] = [];
const leftSymbols = '{[('
const rightSymbols = '}])'

for (let i = 0; i < len; 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
}

三、算法复杂度

其中只包含了一个 for 循环和 pop 操作,所以算法复杂度就是:

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

《数据结构与算法》系列

  1. 什么是算法复杂度
  2. 堆(heap)、栈(stack)、队列(queue)
  3. 把一个数组旋转k步
  4. 判断字符串是否括号匹配
  5. 数组、栈、链表、队列结构与对比
  6. 用两个栈实现一个队列
  7. 反转单向链表
  8. 用链表实现队列
  9. 二分查找
  10. 查找两数之和

欢迎访问:天问博客

本文作者: Tiven
发布时间: 2023-07-12
最后更新: 2023-07-20
本文标题: 【数据结构与算法】(4):判断字符串是否括号匹配
本文链接: https://www.tiven.cn/p/df874343/
版权声明: 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明出处!
欢迎留言,提问 ^_^
个人邮箱: tw.email@qq.com
notification icon
博客有更新,将会发送通知给您!