Leetcode 题目:括号匹配

前言

这道题目是 LeetCode 第 20 题 Valid Parentheses。

在我用 Go 解答这个问题时,发现了 Go 特别的用法和一些求解中容易忽略的边界条件,觉的还是有必要记录一下。

题目简述

给定一个只包含 '(',')','{','}','['和']'的字符串,判断字符串是否有效。有效的条件为:括号必须有相同的括号对应, 且括号必须以正确的顺序对应。

示例1:

输入:"()"
输出:true

示例2:

输入:"()[]{}"
输出: true

示例3:

输入:"([)]"
输出:true

解题思路

遍历字符串每个字符,当字符属于'(','{','['时,将字符压入栈。若字符不属于,则将当前字符与栈顶元素比较,如果括号对应说明正确并弹出栈顶元素,否则返回错误。

依照此思路写下第一个版本的答案:

func isValid(s string) bool {
 brackets := map[rune]rune{')': '(', ']': '[', '}': '{'}
 var stack []rune
 for _, char := range s {
 if char == '(' || char == '{' || char == '[' {
 stack = append(stack, char)
 } else if brackets[char] == stack[len(stack) - 1] {
 stack = stack[:len(stack) - 1]
 } else {
 return false
 }
 }
 return false
}

Go 一般是不会出现单引号的,单引号只能包含一个字符,通过 fmt.Println(reflect.TypeOf('(')) 可以发现它是一个 int32 类型,也就等同于 rune 类型,关于 rune 的解释,可以查看这个博客。字符串底层是 byte,中文在 utf-8 编码下是 3 byte,而是用 unicode 解码就是 1 个字符。

以上代码并不能通过 leetcode 的测试,因为这里忽略了两个测试情况:

• 匹配过程中栈为空。例如{}}
• 匹配结束,stack 还不为空。例如{{}

然后我们修复这个问题:

func isValid(s string) bool {
 brackets := map[rune]rune{')': '(', ']': '[', '}': '{'}
 var stack []rune
 for _, char := range s {
 fmt.Println(reflect.TypeOf(char))
 if char == '(' || char == '{' || char == '[' {
 // 入栈
 stack = append(stack, char)
 // 循环中,stack不能为空
 } else if len(stack) > 0 && brackets[char] == stack[len(stack) - 1] {
 // 栈中有数据,且此元素与栈尾元素相同
 stack = stack[:len(stack) - 1]
 } else {
 return false
 }
 }
 // 循环结束,栈中还有数据则 false
 return len(stack) == 0
}

本文来自:Segmentfault

感谢作者:Donne

查看原文:Leetcode 题目:括号匹配

• 编辑
• 预览