【LeetCode】20. 有效的括号 - Go 语言题解

---

一、题目描述

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

有效字符串需满足：

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

示例 1：
输入：s = "()"
输出：true

示例 2：
输入：s = "()[]{}"
输出：true

示例 3：
输入：s = "(]"
输出：false

示例 4：
输入：s = "([)]"
输出：false

示例 5：
输入：s = "{[]}"
输出：true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

提示：
1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成
1
2
3

题目链接：https://leetcode.cn/problems/valid-parentheses

---

二、题解思路

数据结构：栈

将字符串中的符号依次入栈，若当前栈顶符号和待入栈符号配对，则栈顶出栈。
若不匹配，则入栈。

最终若栈为空，则匹配成功。不为空则匹配失败。

---

三、我的 Go 语言题解

注意：

1. Go 语言中，字符有两种存储类型：byte 和 rune。我用的是 rune。
2. 字符 '(' 和 ')' 的 int 值分别为 40 和 41 。'['，']' 分别为 91 和 93 。'{'，'}' 分别为 123 和 125 。

func isValid(s string) bool {

    
    sli := []rune(s)
    l := len(sli)
    
    if l <= 1 {
        return false
    }
    
    stack := make([]rune, l)
    stack[0] = sli[0]
    //栈顶
    top := 0
    
    if stack[top] == 41 || stack[top] == 93 || stack[top] == 125 {
        return false
    }

    for i:=1; i<l ;i++{
        if top == -1{
            top++
            stack[top] = sli[i]
            continue
        }
        
        
        switch stack[top] {
            case 40:
                if sli[i] != 41 {
                    top++
                    stack[top] = sli[i]
                }else{
                    top--
                }
            case 91:
                if sli[i] != 93 {
                    top++
                    stack[top] = sli[i]
                }else{
                    top--
                }
            case 123:
                if sli[i] != 125 {
                    top++
                    stack[top] = sli[i]
                }else{
                    top--
                }
        }
            
    }  
        
    if top == -1{
        return true
    }else{
        return false
    }

}
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

评判结果：