20. Valid Parentheses

20. 有效的括号

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

1. 栈

由于括号只能和最近的括号配对, 故使用栈来存储括号.

1. 构建哈希表, 存储括号对, 使得查询时间为 $O(1)$
2. 遍历字符串:
   • 若是右括号:
     • 栈为空或栈顶元素不匹配, 不合法
     • 匹配, 栈顶出栈
   • 左括号入栈
3. 遍历结束
   • 栈为空则括号完全匹配
   • 不为空, 还剩下左括号

func isValid(s string) bool {
    if len(s) % 2 == 1 || len(s) == 0 {
        return false
    }

    pairs := map[byte]byte{
        ')': '(',
        ']': '[',
        '}': '{',
    }

    st := []byte{}
    for i := range s {
        c := s[i]
        p, ok := pairs[c]
        
        // 右括号
        if ok {
            // 为空 || 不匹配
            if len(st) == 0 || p != st[len(st)-1] {
                return false
            }
            // 匹配
            st = st[:len(st)-1]
        } else {// 左括号
            st = append(st, c)
        }
    }

    // 合法
    if len(st) == 0 {
        return true
    }

    return false
}

Reference

1. https://leetcode.cn/problems/valid-parentheses/solutions