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

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

一、问题描述

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

示例 1：

• 输入：s = "{(2[a]4)}"
• 输出：true

示例 2：

• 输入：s = "((324[bcd]{231}))"
• 输出：true

示例 3：

• 输入：s = "(({[[()34)]]}))"
• 输出：false

二、代码演示

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. 查找两数之和

欢迎访问：天问博客