20. 有效的括号

leecode原题

题目

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

有效字符串需满足：

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

示例

示例 1:

输入：s = "()"
输出：true

示例 2:

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

示例 3:

输入：s = "(]"
输出：false

示例 4:

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

示例 5:

输入：s = "{[]}"
输出：true

提示：

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

解题思路

思路

该题是一个很典型的使用栈解决问题的经典题目。

具体思路就是:

遍历字符串:

• 情况1: 遇到左括号，直接将左括号对应的右括号入栈
• 情况2: 栈非空, 且右括号和栈顶元素相等，则弹出栈顶元素
• 其他情况: 代表不匹配(比如遇到右括号，但是栈非空，或者右括号和栈顶元素不相同)

遍历完成之后, 栈不为空的话(比如最后都是连续的几个左括号)，则也代表不匹配。

实现

源码

func isValid(s string) bool {
    n := len(s)
    if n == 0 {
        return true
    }
    stack := []byte{} // 用数组实现一个栈
    // 字符括号映射表
    charMap := map[byte]byte{
        '{': '}',
        '(': ')',
        '[': ']',
    }
    for i := 0; i < n; i++ {
        // 如果是左括号，则直接将其对应的右括号入栈
        if s[i] == '{' || s[i] == '(' || s[i] == '[' {
            stack = append(stack, charMap[s[i]])
        } else if len(stack) > 0 && s[i] == stack[len(stack)-1] {
            // 当前字符映射匹配到栈首元素, 栈弹出
            stack = stack[:len(stack)-1]
        } else {
            return false
        }
    }
    // 最终判断栈是否为空
    if len(stack) != 0 {
        return false
    }
    return true
}