LeetCode 20 有效的括号

题目:

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

有效字符串需满足:

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

解题:

和栈一样,先进后出匹配就可以

代码:


func isValid(s string) bool {
    if len(s)%2 > 0 {
        return false
    }
    table := map[byte]byte{'(': ')', '[': ']', '{': '}'}
    var stack []byte
    for i := range s {
        if table[s[i]] > 0 {
            stack = append(stack, table[s[i]])
        } else {
            if len(stack) == 0 || stack[len(stack)-1] != s[i] {
                return false
            }
            stack = stack[:len(stack)-1]
        }
    }
    return len(stack) == 0
}

官方解答: 

// 栈
func isValid(s string) bool {
    n := len(s)
    if n % 2 == 1 {
        return false
    }
    pairs := map[byte]byte{
        ')': '(',
        ']': '[',
        '}': '{',
    }
    stack := []byte{}
    for i := 0; i < n; i++ {
        if pairs[s[i]] > 0 {
            if len(stack) == 0 || stack[len(stack)-1] != pairs[s[i]] {
                return false
            }
            stack = stack[:len(stack)-1]
        } else {
            stack = append(stack, s[i])
        }
    }
    return len(stack) == 0
}

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注