【数据结构与算法】(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)

《数据结构与算法》系列

欢迎访问：天问博客

#一、问题描述

#二、代码演示

#三、算法复杂度

#《数据结构与算法》系列

一、问题描述

二、代码演示

三、算法复杂度

《数据结构与算法》系列