1. 题目

1.1 英文

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

1.2 中文

给予一个包含'(', ')', '{', '}', '[' 和 ']'的字符串，检查该字符串是否有效；括弧必须正确地用另一边关闭，就像"()" and "()[]{}"，不能"(]"或者"([)]"。

2. 解答

看到这道题，第一反应就是用栈来做，将匹配的左括弧压栈然后匹配。

用简单的方式来实现。
接下来用go语言来实现，利用切片做一个类似栈的中间存储，匹配最后一个就可以。因为括弧就只有这三种，所以事先利用字典定义好括弧的集合用于匹配。

var OpenP map[byte]byte = map[byte]byte{'(':')' , '[':']', '{':'}'}
var CloseP map[byte]byte = map[byte]byte{')':'(' , ']':'[', '}':'{'}

func isValid(s string) bool {
    buf := make([]byte, 0, len(s))

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

        // 如果是左半部分；存进切片中
        if _, ok := OpenP[c]; ok{
            buf = append(buf,c)
            continue
        }

        // 如果不是左半部分，进行判断
        openOne := CloseP[c] // c对应的前半部分
        bufLen := len(buf)
        // buf中没有，或者 最后一个buf[bufLen-1]和当前c对应的前半部分不匹配；
        if len(buf) <= 0 || buf[bufLen-1] != openOne{
            return false
        }

        // 匹配到了，切割切片，将c和c对应的前半部分（最后一个）切掉
        buf = buf[:bufLen-1]
    }

    // 最后buf不应该有东西
    return len(buf)==0
}