LeetCode: Valid Parentheses

Posted on January 11, 2018July 26, 2020 by braindenny

Valid Parentheses

Similar Problems:

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.

Leave me comments, if you have better ways to solve.

// https://code.dennyzhang.com/valid-parentheses
// Basic Ideas: stack
// Complexity: Time O(n), Space O(n)
func isValid(s string) bool {
    stack := []byte{}
    m := map[byte]byte{')':'(', ']':'[', '}':'{'}
    for i, _ := range s {
        ch := byte(s[i])
        if _, ok := m[ch]; ok {
            if len(stack)<1 || stack[len(stack)-1] != m[ch] {
                return false
            }
            stack = stack[0:len(stack)-1]
        } else {
            stack = append(stack, ch)
        }
    }
    return len(stack) == 0
}

Post Views: 8