20. 有效的括号
给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
解法一:
空间复杂度:$O(n)$
时间复杂度:$O(n)$
func isValid(s string) bool {
//空串认为是合法的
if s == ""{
return true
}
//如果s长度为奇数是不可能合法的
if len(s) % 2 == 1 {
return false
}
temStr := ""
//把括号分为两类,左类和右类
myMap := map[byte]byte{
'(': ')',
'[': ']',
'{': '}',
}
//遍历s
//1.如果s[i]为左类就添加到temstr中
//2.如果s[i]为右类就看temstr和s[i]是否匹配
//匹配则减去temstr的一个长度
//不匹配则返回false
for i, _ := range s {
if temStr == "" {
temStr = temStr + s[i:i + 1]
continue
}
if _, ok := myMap[s[i]]; !ok {
if myMap[temStr[len(temStr) - 1]] != s[i] {
return false
}
temStr = temStr[:len(temStr) - 1]
} else {
temStr = temStr + s[i:i + 1]
}
}
//如果最后temstr为空说明括号合法
return temStr == ""
}