简单-有效的括号
2019-01-09 本文已影响5人
拾丨玖
- 给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。
示例 1: 输入: "()" 输出: true
示例 2: 输入: "()[]{}" 输出: true
示例 3: 输入: "(]" 输出: false
示例 4: 输入: "([)]" 输出: false
示例 5: 输入: "{[]}" 输出: true
// 比较容易理解
func IsValid(s string) bool {
var flag int
for {
flag = 0
if strings.Contains(s, "()") {
s = strings.Replace(s, "()", "", -1)
} else {
flag += 1
}
if strings.Contains(s, "[]") {
s = strings.Replace(s, "[]", "", -1)
} else {
flag += 1
}
if strings.Contains(s, "{}") {
s = strings.Replace(s, "{}", "", -1)
}else {
flag += 1
}
if flag == 3 {
break
}
}
if len(s) == 0 {
return true
} else {
return false
}
}
// 引入栈
func isValid(s string) bool {
size := len(s)
stack := make([]byte, size)
top := 0
for i := 0; i < size; i++ {
c := s[i]
switch c {
case '(':
stack[top] = c + 1 // '('+1 is ')'
top++
case '[', '{':
stack[top] = c + 2
top++
case ')', ']', '}':
if top > 0 && stack[top-1] == c {
top--
} else {
return false
}
}
}
return top == 0
}