题目地址(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 为数组长度。
- 时间复杂度：
- 空间复杂度：
