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
}