本系列文章为《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
}