网站导航
> 技术文档 > 【华为机试】20. 有效的括号

【华为机试】20. 有效的括号

网友: 技术文档 2025-07-30 13:40:07

文章目录

  • 20. 有效的括号
    • 描述
    • 示例 1
    • 示例 2
    • 示例 3
    • 示例 4
    • 示例 5
    • 提示
    • 解题思路
      • 算法分析
      • 问题本质分析
      • 栈匹配算法详解
      • 括号匹配过程演示
      • 不匹配情况分析
      • 算法流程图
      • 各种解法对比
      • 栈操作示意图
      • 边界情况处理
      • 时间复杂度分析
      • 空间复杂度分析
      • 关键优化点
      • 实际应用场景
      • 测试用例设计
      • 代码实现要点
    • 完整题解代码

20. 有效的括号

描述

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1

输入：s = “()”

输出：true

示例 2

输入：s = “()[]{}”

输出：true

示例 3

输入：s = “(]”

输出：false

示例 4

输入：s = “([])”

输出：true

示例 5

输入：s = “([)]”

输出：false

提示

1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成

解题思路

算法分析

这道题是栈数据结构的经典应用。主要解法包括：

  1. 栈匹配法：使用栈存储左括号，遇到右括号时匹配栈顶
  2. 计数器法：分别计数三种括号的开闭状态
  3. 替换法：不断替换匹配的括号对直到无法替换

问题本质分析

graph TD A[有效的括号] --> B[括号匹配问题] B --> C[栈匹配策略] B --> D[计数策略] B --> E[替换策略] C --> F[栈存储左括号] D --> G[三个计数器] E --> H[字符串替换] F --> I[时间复杂度O_n空间复杂度O_n] G --> J[时间复杂度O_n空间复杂度O_1] H --> K[时间复杂度O_n²空间复杂度O_n]

栈匹配算法详解

#mermaid-svg-WJCWxshaI76eOv5y {font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-WJCWxshaI76eOv5y .error-icon{fill:#552222;}#mermaid-svg-WJCWxshaI76eOv5y .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-WJCWxshaI76eOv5y .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-WJCWxshaI76eOv5y .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-WJCWxshaI76eOv5y .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-WJCWxshaI76eOv5y .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-WJCWxshaI76eOv5y .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-WJCWxshaI76eOv5y .marker{fill:#333333;stroke:#333333;}#mermaid-svg-WJCWxshaI76eOv5y .marker.cross{stroke:#333333;}#mermaid-svg-WJCWxshaI76eOv5y svg{font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-WJCWxshaI76eOv5y .label{font-family:\"trebuchet ms\",verdana,arial,sans-serif;color:#333;}#mermaid-svg-WJCWxshaI76eOv5y .cluster-label text{fill:#333;}#mermaid-svg-WJCWxshaI76eOv5y .cluster-label span{color:#333;}#mermaid-svg-WJCWxshaI76eOv5y .label text,#mermaid-svg-WJCWxshaI76eOv5y span{fill:#333;color:#333;}#mermaid-svg-WJCWxshaI76eOv5y .node rect,#mermaid-svg-WJCWxshaI76eOv5y .node circle,#mermaid-svg-WJCWxshaI76eOv5y .node ellipse,#mermaid-svg-WJCWxshaI76eOv5y .node polygon,#mermaid-svg-WJCWxshaI76eOv5y .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-WJCWxshaI76eOv5y .node .label{text-align:center;}#mermaid-svg-WJCWxshaI76eOv5y .node.clickable{cursor:pointer;}#mermaid-svg-WJCWxshaI76eOv5y .arrowheadPath{fill:#333333;}#mermaid-svg-WJCWxshaI76eOv5y .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-WJCWxshaI76eOv5y .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-WJCWxshaI76eOv5y .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-WJCWxshaI76eOv5y .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-WJCWxshaI76eOv5y .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-WJCWxshaI76eOv5y .cluster text{fill:#333;}#mermaid-svg-WJCWxshaI76eOv5y .cluster span{color:#333;}#mermaid-svg-WJCWxshaI76eOv5y div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-WJCWxshaI76eOv5y :root{--mermaid-font-family:\"trebuchet ms\",verdana,arial,sans-serif;} 左括号 右括号 空 非空 匹配 不匹配 否 是 空 非空 输入字符串s 初始化空栈 遍历字符串 当前字符类型 压入栈中 栈是否为空 继续下一字符 返回false 取栈顶元素 括号是否匹配 弹出栈顶 是否遍历完成 栈是否为空 返回true

括号匹配过程演示

graph TD A[\"输入: \'([{}])\'\"] --> B[遍历过程] B --> C[\"\'(\' → 栈: [\'(\']\"] C --> D[\"\'[\' → 栈: [\'(\', \'[\']\"] D --> E[\"\'{\' → 栈: [\'(\', \'[\', \'{\']\"] E --> F[\"\'}\' → 匹配\'{\' → 栈: [\'(\', \'[\']\"] F --> G[\"\']\' → 匹配\'[\' → 栈: [\'(\']\"] G --> H[\"\')\' → 匹配\'(\' → 栈: []\"] H --> I[栈为空，返回true]

不匹配情况分析

#mermaid-svg-qOrEtr8rWjmnM0zy {font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-qOrEtr8rWjmnM0zy .error-icon{fill:#552222;}#mermaid-svg-qOrEtr8rWjmnM0zy .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-qOrEtr8rWjmnM0zy .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-qOrEtr8rWjmnM0zy .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-qOrEtr8rWjmnM0zy .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-qOrEtr8rWjmnM0zy .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-qOrEtr8rWjmnM0zy .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-qOrEtr8rWjmnM0zy .marker{fill:#333333;stroke:#333333;}#mermaid-svg-qOrEtr8rWjmnM0zy .marker.cross{stroke:#333333;}#mermaid-svg-qOrEtr8rWjmnM0zy svg{font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-qOrEtr8rWjmnM0zy .label{font-family:\"trebuchet ms\",verdana,arial,sans-serif;color:#333;}#mermaid-svg-qOrEtr8rWjmnM0zy .cluster-label text{fill:#333;}#mermaid-svg-qOrEtr8rWjmnM0zy .cluster-label span{color:#333;}#mermaid-svg-qOrEtr8rWjmnM0zy .label text,#mermaid-svg-qOrEtr8rWjmnM0zy span{fill:#333;color:#333;}#mermaid-svg-qOrEtr8rWjmnM0zy .node rect,#mermaid-svg-qOrEtr8rWjmnM0zy .node circle,#mermaid-svg-qOrEtr8rWjmnM0zy .node ellipse,#mermaid-svg-qOrEtr8rWjmnM0zy .node polygon,#mermaid-svg-qOrEtr8rWjmnM0zy .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-qOrEtr8rWjmnM0zy .node .label{text-align:center;}#mermaid-svg-qOrEtr8rWjmnM0zy .node.clickable{cursor:pointer;}#mermaid-svg-qOrEtr8rWjmnM0zy .arrowheadPath{fill:#333333;}#mermaid-svg-qOrEtr8rWjmnM0zy .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-qOrEtr8rWjmnM0zy .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-qOrEtr8rWjmnM0zy .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-qOrEtr8rWjmnM0zy .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-qOrEtr8rWjmnM0zy .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-qOrEtr8rWjmnM0zy .cluster text{fill:#333;}#mermaid-svg-qOrEtr8rWjmnM0zy .cluster span{color:#333;}#mermaid-svg-qOrEtr8rWjmnM0zy div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-qOrEtr8rWjmnM0zy :root{--mermaid-font-family:\"trebuchet ms\",verdana,arial,sans-serif;} 不匹配情况 类型不匹配 数量不匹配 顺序不匹配 \'(\' 与 \']\' 不匹配 左括号多：\'(((\' 右括号多：\')))\' 交叉嵌套：\'([)]\' 返回false

算法流程图

#mermaid-svg-RLugcT7YYfIFPlFh {font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-RLugcT7YYfIFPlFh .error-icon{fill:#552222;}#mermaid-svg-RLugcT7YYfIFPlFh .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-RLugcT7YYfIFPlFh .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-RLugcT7YYfIFPlFh .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-RLugcT7YYfIFPlFh .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-RLugcT7YYfIFPlFh .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-RLugcT7YYfIFPlFh .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-RLugcT7YYfIFPlFh .marker{fill:#333333;stroke:#333333;}#mermaid-svg-RLugcT7YYfIFPlFh .marker.cross{stroke:#333333;}#mermaid-svg-RLugcT7YYfIFPlFh svg{font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-RLugcT7YYfIFPlFh .label{font-family:\"trebuchet ms\",verdana,arial,sans-serif;color:#333;}#mermaid-svg-RLugcT7YYfIFPlFh .cluster-label text{fill:#333;}#mermaid-svg-RLugcT7YYfIFPlFh .cluster-label span{color:#333;}#mermaid-svg-RLugcT7YYfIFPlFh .label text,#mermaid-svg-RLugcT7YYfIFPlFh span{fill:#333;color:#333;}#mermaid-svg-RLugcT7YYfIFPlFh .node rect,#mermaid-svg-RLugcT7YYfIFPlFh .node circle,#mermaid-svg-RLugcT7YYfIFPlFh .node ellipse,#mermaid-svg-RLugcT7YYfIFPlFh .node polygon,#mermaid-svg-RLugcT7YYfIFPlFh .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-RLugcT7YYfIFPlFh .node .label{text-align:center;}#mermaid-svg-RLugcT7YYfIFPlFh .node.clickable{cursor:pointer;}#mermaid-svg-RLugcT7YYfIFPlFh .arrowheadPath{fill:#333333;}#mermaid-svg-RLugcT7YYfIFPlFh .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-RLugcT7YYfIFPlFh .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-RLugcT7YYfIFPlFh .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-RLugcT7YYfIFPlFh .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-RLugcT7YYfIFPlFh .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-RLugcT7YYfIFPlFh .cluster text{fill:#333;}#mermaid-svg-RLugcT7YYfIFPlFh .cluster span{color:#333;}#mermaid-svg-RLugcT7YYfIFPlFh div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-RLugcT7YYfIFPlFh :root{--mermaid-font-family:\"trebuchet ms\",verdana,arial,sans-serif;} 是 否 是 否 是 否 是 否 是 否 是 否 开始 初始化栈 获取下一个字符 字符是左括号? 压入栈 字符是右括号? 栈为空? 返回false 获取栈顶元素 括号匹配? 弹出栈顶 还有字符? 栈为空? 返回true

各种解法对比

graph TD A[解法对比] --> B[栈匹配法] A --> C[计数器法] A --> D[替换法] A --> E[递归法] B --> F[时间O_n空间O_n] C --> G[时间O_n空间O_1] D --> H[时间O_n²空间O_n] E --> I[时间O_n空间O_n] F --> J[经典解法推荐] G --> K[空间优化仅限简单情况] H --> L[效率较低不推荐] I --> M[代码简洁但栈深度风险]

栈操作示意图

#mermaid-svg-eQpq374eSpHVweK6 {font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-eQpq374eSpHVweK6 .error-icon{fill:#552222;}#mermaid-svg-eQpq374eSpHVweK6 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-eQpq374eSpHVweK6 .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-eQpq374eSpHVweK6 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-eQpq374eSpHVweK6 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-eQpq374eSpHVweK6 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-eQpq374eSpHVweK6 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-eQpq374eSpHVweK6 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-eQpq374eSpHVweK6 .marker.cross{stroke:#333333;}#mermaid-svg-eQpq374eSpHVweK6 svg{font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-eQpq374eSpHVweK6 .label{font-family:\"trebuchet ms\",verdana,arial,sans-serif;color:#333;}#mermaid-svg-eQpq374eSpHVweK6 .cluster-label text{fill:#333;}#mermaid-svg-eQpq374eSpHVweK6 .cluster-label span{color:#333;}#mermaid-svg-eQpq374eSpHVweK6 .label text,#mermaid-svg-eQpq374eSpHVweK6 span{fill:#333;color:#333;}#mermaid-svg-eQpq374eSpHVweK6 .node rect,#mermaid-svg-eQpq374eSpHVweK6 .node circle,#mermaid-svg-eQpq374eSpHVweK6 .node ellipse,#mermaid-svg-eQpq374eSpHVweK6 .node polygon,#mermaid-svg-eQpq374eSpHVweK6 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-eQpq374eSpHVweK6 .node .label{text-align:center;}#mermaid-svg-eQpq374eSpHVweK6 .node.clickable{cursor:pointer;}#mermaid-svg-eQpq374eSpHVweK6 .arrowheadPath{fill:#333333;}#mermaid-svg-eQpq374eSpHVweK6 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-eQpq374eSpHVweK6 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-eQpq374eSpHVweK6 .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-eQpq374eSpHVweK6 .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-eQpq374eSpHVweK6 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-eQpq374eSpHVweK6 .cluster text{fill:#333;}#mermaid-svg-eQpq374eSpHVweK6 .cluster span{color:#333;}#mermaid-svg-eQpq374eSpHVweK6 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-eQpq374eSpHVweK6 :root{--mermaid-font-family:\"trebuchet ms\",verdana,arial,sans-serif;} 空 非空 匹配 不匹配 栈操作过程 遇到左括号 遇到右括号 PUSH操作 栈空检查 栈顶增加元素 直接返回false POP操作 类型匹配检查 弹出栈顶元素 继续处理下一字符

边界情况处理

#mermaid-svg-CeuqURMbioWikyRy {font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-CeuqURMbioWikyRy .error-icon{fill:#552222;}#mermaid-svg-CeuqURMbioWikyRy .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-CeuqURMbioWikyRy .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-CeuqURMbioWikyRy .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-CeuqURMbioWikyRy .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-CeuqURMbioWikyRy .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-CeuqURMbioWikyRy .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-CeuqURMbioWikyRy .marker{fill:#333333;stroke:#333333;}#mermaid-svg-CeuqURMbioWikyRy .marker.cross{stroke:#333333;}#mermaid-svg-CeuqURMbioWikyRy svg{font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-CeuqURMbioWikyRy .label{font-family:\"trebuchet ms\",verdana,arial,sans-serif;color:#333;}#mermaid-svg-CeuqURMbioWikyRy .cluster-label text{fill:#333;}#mermaid-svg-CeuqURMbioWikyRy .cluster-label span{color:#333;}#mermaid-svg-CeuqURMbioWikyRy .label text,#mermaid-svg-CeuqURMbioWikyRy span{fill:#333;color:#333;}#mermaid-svg-CeuqURMbioWikyRy .node rect,#mermaid-svg-CeuqURMbioWikyRy .node circle,#mermaid-svg-CeuqURMbioWikyRy .node ellipse,#mermaid-svg-CeuqURMbioWikyRy .node polygon,#mermaid-svg-CeuqURMbioWikyRy .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-CeuqURMbioWikyRy .node .label{text-align:center;}#mermaid-svg-CeuqURMbioWikyRy .node.clickable{cursor:pointer;}#mermaid-svg-CeuqURMbioWikyRy .arrowheadPath{fill:#333333;}#mermaid-svg-CeuqURMbioWikyRy .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-CeuqURMbioWikyRy .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-CeuqURMbioWikyRy .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-CeuqURMbioWikyRy .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-CeuqURMbioWikyRy .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-CeuqURMbioWikyRy .cluster text{fill:#333;}#mermaid-svg-CeuqURMbioWikyRy .cluster span{color:#333;}#mermaid-svg-CeuqURMbioWikyRy div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-CeuqURMbioWikyRy :root{--mermaid-font-family:\"trebuchet ms\",verdana,arial,sans-serif;} 边界情况 空字符串 单个字符 只有左括号 只有右括号 最大长度 返回true 单个字符必定false 栈非空返回false 栈空时遇右括号返回false 正常处理无特殊逻辑

时间复杂度分析

  • 栈匹配法：O(n)，每个字符访问一次
  • 计数器法：O(n)，但只适用于单一类型括号
  • 替换法：O(n²)，需要多次遍历字符串
  • 递归法：O(n)，但有栈溢出风险

空间复杂度分析

  • 栈匹配法：O(n)，最坏情况栈存储n/2个左括号
  • 计数器法：O(1)，只需要常数个计数器
  • 替换法：O(n)，需要创建新字符串
  • 递归法：O(n)，递归调用栈空间

关键优化点

#mermaid-svg-xdIU9RKnChrpkMuH {font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-xdIU9RKnChrpkMuH .error-icon{fill:#552222;}#mermaid-svg-xdIU9RKnChrpkMuH .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-xdIU9RKnChrpkMuH .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-xdIU9RKnChrpkMuH .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-xdIU9RKnChrpkMuH .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-xdIU9RKnChrpkMuH .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-xdIU9RKnChrpkMuH .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-xdIU9RKnChrpkMuH .marker{fill:#333333;stroke:#333333;}#mermaid-svg-xdIU9RKnChrpkMuH .marker.cross{stroke:#333333;}#mermaid-svg-xdIU9RKnChrpkMuH svg{font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-xdIU9RKnChrpkMuH .label{font-family:\"trebuchet ms\",verdana,arial,sans-serif;color:#333;}#mermaid-svg-xdIU9RKnChrpkMuH .cluster-label text{fill:#333;}#mermaid-svg-xdIU9RKnChrpkMuH .cluster-label span{color:#333;}#mermaid-svg-xdIU9RKnChrpkMuH .label text,#mermaid-svg-xdIU9RKnChrpkMuH span{fill:#333;color:#333;}#mermaid-svg-xdIU9RKnChrpkMuH .node rect,#mermaid-svg-xdIU9RKnChrpkMuH .node circle,#mermaid-svg-xdIU9RKnChrpkMuH .node ellipse,#mermaid-svg-xdIU9RKnChrpkMuH .node polygon,#mermaid-svg-xdIU9RKnChrpkMuH .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-xdIU9RKnChrpkMuH .node .label{text-align:center;}#mermaid-svg-xdIU9RKnChrpkMuH .node.clickable{cursor:pointer;}#mermaid-svg-xdIU9RKnChrpkMuH .arrowheadPath{fill:#333333;}#mermaid-svg-xdIU9RKnChrpkMuH .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-xdIU9RKnChrpkMuH .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-xdIU9RKnChrpkMuH .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-xdIU9RKnChrpkMuH .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-xdIU9RKnChrpkMuH .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-xdIU9RKnChrpkMuH .cluster text{fill:#333;}#mermaid-svg-xdIU9RKnChrpkMuH .cluster span{color:#333;}#mermaid-svg-xdIU9RKnChrpkMuH div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-xdIU9RKnChrpkMuH :root{--mermaid-font-family:\"trebuchet ms\",verdana,arial,sans-serif;} 优化策略 提前终止 字符映射 栈容量预分配 字符数组优化 奇数长度直接返回false 使用map快速匹配 避免栈动态扩容 避免字符串操作开销 性能提升

实际应用场景

#mermaid-svg-04lIJXNErsD21X7v {font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-04lIJXNErsD21X7v .error-icon{fill:#552222;}#mermaid-svg-04lIJXNErsD21X7v .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-04lIJXNErsD21X7v .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-04lIJXNErsD21X7v .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-04lIJXNErsD21X7v .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-04lIJXNErsD21X7v .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-04lIJXNErsD21X7v .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-04lIJXNErsD21X7v .marker{fill:#333333;stroke:#333333;}#mermaid-svg-04lIJXNErsD21X7v .marker.cross{stroke:#333333;}#mermaid-svg-04lIJXNErsD21X7v svg{font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-04lIJXNErsD21X7v .label{font-family:\"trebuchet ms\",verdana,arial,sans-serif;color:#333;}#mermaid-svg-04lIJXNErsD21X7v .cluster-label text{fill:#333;}#mermaid-svg-04lIJXNErsD21X7v .cluster-label span{color:#333;}#mermaid-svg-04lIJXNErsD21X7v .label text,#mermaid-svg-04lIJXNErsD21X7v span{fill:#333;color:#333;}#mermaid-svg-04lIJXNErsD21X7v .node rect,#mermaid-svg-04lIJXNErsD21X7v .node circle,#mermaid-svg-04lIJXNErsD21X7v .node ellipse,#mermaid-svg-04lIJXNErsD21X7v .node polygon,#mermaid-svg-04lIJXNErsD21X7v .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-04lIJXNErsD21X7v .node .label{text-align:center;}#mermaid-svg-04lIJXNErsD21X7v .node.clickable{cursor:pointer;}#mermaid-svg-04lIJXNErsD21X7v .arrowheadPath{fill:#333333;}#mermaid-svg-04lIJXNErsD21X7v .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-04lIJXNErsD21X7v .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-04lIJXNErsD21X7v .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-04lIJXNErsD21X7v .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-04lIJXNErsD21X7v .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-04lIJXNErsD21X7v .cluster text{fill:#333;}#mermaid-svg-04lIJXNErsD21X7v .cluster span{color:#333;}#mermaid-svg-04lIJXNErsD21X7v div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-04lIJXNErsD21X7v :root{--mermaid-font-family:\"trebuchet ms\",verdana,arial,sans-serif;} 应用场景 编译器设计 文本编辑器 表达式解析 XML/HTML解析 语法分析器 括号匹配高亮 数学表达式求值 标签匹配验证 核心算法组件

测试用例设计

#mermaid-svg-VgDbpMvDNXYbwjiA {font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-VgDbpMvDNXYbwjiA .error-icon{fill:#552222;}#mermaid-svg-VgDbpMvDNXYbwjiA .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-VgDbpMvDNXYbwjiA .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-VgDbpMvDNXYbwjiA .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-VgDbpMvDNXYbwjiA .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-VgDbpMvDNXYbwjiA .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-VgDbpMvDNXYbwjiA .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-VgDbpMvDNXYbwjiA .marker{fill:#333333;stroke:#333333;}#mermaid-svg-VgDbpMvDNXYbwjiA .marker.cross{stroke:#333333;}#mermaid-svg-VgDbpMvDNXYbwjiA svg{font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-VgDbpMvDNXYbwjiA .label{font-family:\"trebuchet ms\",verdana,arial,sans-serif;color:#333;}#mermaid-svg-VgDbpMvDNXYbwjiA .cluster-label text{fill:#333;}#mermaid-svg-VgDbpMvDNXYbwjiA .cluster-label span{color:#333;}#mermaid-svg-VgDbpMvDNXYbwjiA .label text,#mermaid-svg-VgDbpMvDNXYbwjiA span{fill:#333;color:#333;}#mermaid-svg-VgDbpMvDNXYbwjiA .node rect,#mermaid-svg-VgDbpMvDNXYbwjiA .node circle,#mermaid-svg-VgDbpMvDNXYbwjiA .node ellipse,#mermaid-svg-VgDbpMvDNXYbwjiA .node polygon,#mermaid-svg-VgDbpMvDNXYbwjiA .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-VgDbpMvDNXYbwjiA .node .label{text-align:center;}#mermaid-svg-VgDbpMvDNXYbwjiA .node.clickable{cursor:pointer;}#mermaid-svg-VgDbpMvDNXYbwjiA .arrowheadPath{fill:#333333;}#mermaid-svg-VgDbpMvDNXYbwjiA .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-VgDbpMvDNXYbwjiA .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-VgDbpMvDNXYbwjiA .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-VgDbpMvDNXYbwjiA .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-VgDbpMvDNXYbwjiA .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-VgDbpMvDNXYbwjiA .cluster text{fill:#333;}#mermaid-svg-VgDbpMvDNXYbwjiA .cluster span{color:#333;}#mermaid-svg-VgDbpMvDNXYbwjiA div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-VgDbpMvDNXYbwjiA :root{--mermaid-font-family:\"trebuchet ms\",verdana,arial,sans-serif;} 测试用例 基础功能 边界情况 性能测试 简单匹配 复杂嵌套 混合括号 空字符串 单字符 不匹配情况 最大长度 大量嵌套 验证正确性 验证性能

代码实现要点

  1. 栈数据结构选择：

    • Go语言使用切片模拟栈
    • 入栈操作：append()
    • 出栈操作：切片截取

  2. 括号匹配映射：

    • 使用map存储括号对应关系
    • 快速查找匹配的左括号

  3. 边界条件处理：

    • 字符串长度为奇数直接返回false
    • 栈为空时遇到右括号返回false
    • 遍历结束后检查栈是否为空

  4. 性能优化：

    • 提前返回减少不必要计算
    • 使用局部变量减少重复计算
    • 合理的数据结构选择

这个问题的关键在于理解栈的后进先出特性和掌握括号匹配的基本规则，通过栈来暂存待匹配的左括号，实现高效的括号有效性检查。

完整题解代码

package mainimport (\"fmt\"\"strings\"\"time\")// 解法一：栈匹配法（推荐解法）// 时间复杂度：O(n)，空间复杂度：O(n)func isValid(s string) bool {// 奇数长度的字符串不可能有效if len(s)%2 == 1 {return false}// 括号映射表：右括号 -> 左括号pairs := map[byte]byte{\')\': \'(\',\']\': \'[\',\'}\': \'{\',}// 使用切片模拟栈stack := []byte{}for i := 0; i < len(s); i++ {char := s[i]// 如果是右括号if pair, exists := pairs[char]; exists {// 栈为空或栈顶元素不匹配if len(stack) == 0 || stack[len(stack)-1] != pair {return false}// 弹出栈顶元素（匹配成功）stack = stack[:len(stack)-1]} else {// 如果是左括号，压入栈中stack = append(stack, char)}}// 栈为空表示所有括号都匹配return len(stack) == 0}// 解法二：替换法// 时间复杂度：O(n²)，空间复杂度：O(n)func isValidReplace(s string) bool {// 不断替换匹配的括号对for len(s) > 0 {oldLen := len(s)// 替换所有可能的括号对s = replaceAll(s, \"()\", \"\")s = replaceAll(s, \"[]\", \"\")s = replaceAll(s, \"{}\", \"\")// 如果没有任何替换发生，说明无法继续匹配if len(s) == oldLen {break}}return len(s) == 0}// 简单的字符串替换函数func replaceAll(s, old, new string) string {result := \"\"i := 0for i < len(s) {if i <= len(s)-len(old) && s[i:i+len(old)] == old {result += newi += len(old)} else {result += string(s[i])i++}}return result}// 解法三：计数器法（仅适用于单一类型括号）// 时间复杂度：O(n)，空间复杂度：O(1)func isValidSimple(s string) bool {// 仅处理圆括号的情况count := 0for i := 0; i < len(s); i++ {if s[i] == \'(\' {count++} else if s[i] == \')\' {count--// 右括号过多if count < 0 {return false}}}return count == 0}// 解法四：递归法// 时间复杂度：O(n)，空间复杂度：O(n)func isValidRecursive(s string) bool {return isValidHelper(s, 0, []byte{})}func isValidHelper(s string, index int, stack []byte) bool {// 递归终止条件if index == len(s) {return len(stack) == 0}char := s[index]pairs := map[byte]byte{\')\': \'(\',\']\': \'[\',\'}\': \'{\',}// 如果是右括号if pair, exists := pairs[char]; exists {// 栈为空或栈顶不匹配if len(stack) == 0 || stack[len(stack)-1] != pair {return false}// 弹出栈顶，继续递归return isValidHelper(s, index+1, stack[:len(stack)-1])} else {// 如果是左括号，压入栈中继续递归newStack := make([]byte, len(stack)+1)copy(newStack, stack)newStack[len(stack)] = charreturn isValidHelper(s, index+1, newStack)}}// 解法五：优化栈法（预分配容量）// 时间复杂度：O(n)，空间复杂度：O(n)func isValidOptimized(s string) bool {n := len(s)if n%2 == 1 {return false}// 预分配栈容量，避免动态扩容stack := make([]byte, 0, n/2)for i := 0; i < n; i++ {char := s[i]switch char {case \'(\':stack = append(stack, char)case \')\':if len(stack) == 0 || stack[len(stack)-1] != \'(\' {return false}stack = stack[:len(stack)-1]case \'[\':stack = append(stack, char)case \']\':if len(stack) == 0 || stack[len(stack)-1] != \'[\' {return false}stack = stack[:len(stack)-1]case \'{\':stack = append(stack, char)case \'}\':if len(stack) == 0 || stack[len(stack)-1] != \'{\' {return false}stack = stack[:len(stack)-1]}}return len(stack) == 0}// 测试函数func testIsValid() {testCases := []struct {input stringexpected booldesc string}{{\"()\", true, \"简单圆括号\"},{\"()[]{}\", true, \"三种括号组合\"},{\"(]\", false, \"类型不匹配\"},{\"([])\", true, \"嵌套括号\"},{\"([)]\", false, \"交叉嵌套\"},{\"\", true, \"空字符串\"},{\"(\", false, \"单个左括号\"},{\")\", false, \"单个右括号\"},{\"((\", false, \"只有左括号\"},{\"))\", false, \"只有右括号\"},{\"(())\", true, \"双层嵌套\"},{\"({[]})\", true, \"多层复杂嵌套\"},{\"({[}])\", false, \"错误的嵌套顺序\"},{\"((()))\", true, \"深度嵌套\"},{\"{[]}\", true, \"不同类型嵌套\"},}fmt.Println(\"=== 有效的括号测试 ===\\n\")for i, tc := range testCases {// 测试主要解法result1 := isValid(tc.input)result2 := isValidOptimized(tc.input)result3 := isValidRecursive(tc.input)status := \"✅\"if result1 != tc.expected {status = \"❌\"}fmt.Printf(\"测试 %d: %s\\n\", i+1, tc.desc)fmt.Printf(\"输入: \\\"%s\\\"\\n\", tc.input)fmt.Printf(\"期望: %t\\n\", tc.expected)fmt.Printf(\"栈法: %t\\n\", result1)fmt.Printf(\"优化: %t\\n\", result2)fmt.Printf(\"递归: %t\\n\", result3)fmt.Printf(\"结果: %s\\n\", status)fmt.Println(strings.Repeat(\"-\", 30))}}// 性能测试func benchmarkIsValid() {fmt.Println(\"\\n=== 性能测试 ===\\n\")// 构造测试数据testData := []string{generateValidBrackets(100), // 短字符串generateValidBrackets(1000), // 中等字符串generateValidBrackets(5000), // 长字符串}algorithms := []struct {name stringfn func(string) bool}{{\"栈匹配法\", isValid},{\"优化栈法\", isValidOptimized},{\"递归法\", isValidRecursive},{\"替换法\", isValidReplace},}for i, data := range testData {fmt.Printf(\"测试数据 %d (长度: %d):\\n\", i+1, len(data))for _, algo := range algorithms {start := time.Now()result := algo.fn(data)duration := time.Since(start)fmt.Printf(\" %s: %t, 耗时: %v\\n\", algo.name, result, duration)}fmt.Println()}}// 生成有效的括号字符串用于测试func generateValidBrackets(n int) string {if n%2 == 1 {n-- // 确保是偶数}result := make([]byte, 0, n)pairs := n / 2// 生成嵌套的括号for i := 0; i < pairs; i++ {bracketType := i % 3switch bracketType {case 0:result = append(result, \'(\')case 1:result = append(result, \'[\')case 2:result = append(result, \'{\')}}// 添加对应的右括号for i := pairs - 1; i >= 0; i-- {bracketType := i % 3switch bracketType {case 0:result = append(result, \')\')case 1:result = append(result, \']\')case 2:result = append(result, \'}\')}}return string(result)}func main() {fmt.Println(\"20. 有效的括号 - 多种解法实现\")fmt.Println(\"========================================\")// 基础功能测试testIsValid()// 性能对比测试benchmarkIsValid()// 展示算法特点fmt.Println(\"\\n=== 算法特点分析 ===\")fmt.Println(\"1. 栈匹配法：经典解法，时间O(n)，空间O(n)，推荐使用\")fmt.Println(\"2. 优化栈法：预分配容量，避免动态扩容，性能略优\")fmt.Println(\"3. 递归法：代码简洁，但可能栈溢出，适合教学\")fmt.Println(\"4. 替换法：思路直观，但效率较低O(n²)，不推荐\")fmt.Println(\"5. 计数器法：仅适用于单一类型括号，空间O(1)\")fmt.Println(\"\\n=== 关键技巧总结 ===\")fmt.Println(\"• 使用map建立括号对应关系，提高查找效率\")fmt.Println(\"• 奇数长度字符串可以提前返回false\")fmt.Println(\"• 栈为空时遇到右括号立即返回false\")fmt.Println(\"• 预分配栈容量可以避免动态扩容开销\")fmt.Println(\"• 选择合适的数据结构是性能优化的关键\")}
网络标签：

相关问题