LeetCode:有效的括号


题目

给定一个只包括 '('')''{''}''['']' 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

  • 左括号必须用相同类型的右括号闭合。
  • 左括号必须以正确的顺序闭合。

示例 1:

1
2
输入:s = "()"
输出:true

示例 2:

1
2
输入:s = "()[]{}"
输出:true

示例 3:

1
2
输入:s = "(]"
输出:false

示例 4:

1
2
输入:s = "([)]"
输出:false

示例 5:

1
2
输入:s = "{[]}"
输出:true

提示:

  • 1 <= s.length <= 10^4
  • s 仅由括号 '()[]{}' 组成

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/valid-parentheses

代码

Go

普通写法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
package main

import (
"fmt"
"strings"
)

func isValid(s string) bool {
for {
o := s

s = strings.Replace(s, "()", "", -1)
s = strings.Replace(s, "[]", "", -1)
s = strings.Replace(s, "{}", "", -1)

if o == s {
break
}
}

return s == ""
}

func main() {
fmt.Println(isValid("()"))
fmt.Println(isValid("()[]{}"))
fmt.Println(isValid("{[]}"))
fmt.Println(isValid("[{}]"))
}

堆栈写法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
package main

import (
"fmt"
)

func isValid(s string) bool {
stack := []string{}

config := map[string]string{
")": "(",
"]": "[",
"}": "{",
}

for i := 0; i < len(s); i++ {
stri := string(s[i])

// 如果遇到左括号,就开始堆栈
if stri == "(" || stri == "[" || stri == "{" {
stack = append(stack, stri)
} else { // 否则从栈最右边进行比较和对比
if len(stack) == 0 || stack[len(stack)-1] != config[stri] {
return false
}

stack = stack[:len(stack)-1]
}

}

return len(stack) == 0
}

func main() {
fmt.Println(isValid("()"))
fmt.Println(isValid("()[]{}"))
fmt.Println(isValid("{[]}"))
fmt.Println(isValid("[{}]"))
}

评论