前言
本系列文章为《leetcode》刷题笔记。
刷题平台：力扣中国
题目
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()" 输出: true
示例 2:
输入: "()[]{}" 输出: true
示例 3:
输入: "(]" 输出: false
示例 4:
输入: "([)]" 输出: false
示例 5:
输入: "{[]}" 输出: true
思路
这是一个典型的逆波兰式，我的思路是利用栈先入后出的特点来解这一题。遍历一遍，遇到左括号就入栈，遇到右括号就出栈，前提是出栈之前需要判断栈顶最后一个元素是否和右括号成对，遇到其他就跳过。
边界条件：
- 字符串内的字符串是奇数个，直接返回
false(仅适用于 只有 括号的情况，如果有字母就不行了) - 没有左括号，就没有入栈，所以需要判断栈长度
- 括号包括号
{[]}
时间复杂度 O(N)：正确的括号组合需要遍历 1 遍 s；
空间复杂度 O(N)：哈希表和栈使用线性的空间大小。
代码
Go
func isLeft(c uint8) bool { return ('{' == c) || ('[' == c) || ('(' == c) } func isRight(c uint8) bool { return ('}' == c) || (']' == c) || (')' == c) } func isOk(c1 uint8, c2 uint8) bool { return ('{' == c1 && c2 == '}') || ('[' == c1 && ']' == c2) || ('(' == c1 && ')' == c2) } func isValid(s string) bool { if len(s)%2!=0 { return false } stack := make([]uint8, len(s)) current := -1 for i := 0; i < len(s); i++ { if isLeft(s[i]) { current++ stack[current] = s[i] } else if isRight(s[i]) { if current != -1 && isOk(stack[current], s[i]) { current-- } else { return false } } } return current == -1 }
