20. 有效的括号

题目地址(20. 有效的括号)

https://leetcode.cn/problems/valid-parentheses/

题目描述

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

前置知识

公司

思路

• 对于最近相关性题目，一般首先考虑使用栈

关键点

• Go的栈，这里使用切片实现
• 特别注意else if len(stack) > 0 && stack[len(stack) - 1] == s[i]中第一个条件

代码

• 语言支持：Go

Go Code:

func isValid(s string) bool {
    if len(s) % 2 == 1 {
        return false
    }
    n := len(s)
    stack := make([]byte, 0)

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

复杂度分析

令 n 为数组长度。

• 时间复杂度：
• 空间复杂度：