LeetCode 20. 有效的括号

题目链接：LeetCode 20. 有效的括号

题意：

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

解题思路：

括号匹配是栈的经典应用场景，具体操作如下：
1. 对于所有的左括号，进栈
2. 对于所有的右括号，弹出栈顶元素，判断是否与当前元素匹配，若不匹配，则return false
3. 最后判断栈中是否还有元素，如果还有剩余元素，则说明有多余括号，不匹配

完整代码如下：

func isValid(s string) bool {
    ss:=[]rune(s)
    n:=len(ss)
    if n % 2 == 1{
        return false
    }
    var st []rune
    for i:=0;i<n;i++{
        if ss[i] == '(' || ss[i] == '{' || ss[i] == '['{
            //入栈
            st = append(st,ss[i])
        }else{
            m:=len(st)
            if m == 0{
                return false
            }
            tmp := st[m-1]
            st = st[:m-1]
            if ss[i] == '}' && tmp != '{' || ss[i] == ')' && tmp != '(' || ss[i] == ']' && tmp != '['{
                return false
            }
        }
    }
    k:=len(st)
    return k==0 
}

也可以结合map简化操作，代码如下：

func isValid(s string) bool {
    hash := map[byte]byte{')':'(', ']':'[', '}':'{'}
    stack := make([]byte, 0)
    if s == "" {
        return true
    }

    for i := 0; i < len(s); i++ {
        if s[i] == '(' || s[i] == '[' || s[i] == '{' {
            stack = append(stack, s[i])
        } else if len(stack) > 0 && stack[len(stack)-1] == hash[s[i]] {
            stack = stack[:len(stack)-1]
        } else {
            return false
        }
    }
    return len(stack) == 0
}