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

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 TDA[有效的括号] --> 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]

栈匹配算法详解

括号匹配过程演示

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

不匹配情况分析

算法流程图

各种解法对比

graph TDA[解法对比] --> 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[代码简洁但栈深度风险]

栈操作示意图

边界情况处理

时间复杂度分析

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

空间复杂度分析

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

关键优化点

实际应用场景

测试用例设计

代码实现要点

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("• 选择合适的数据结构是性能优化的关键")
}