20-有效的括号

题目描述

原题链接

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

有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。

/*
 * @lc app=leetcode.cn id=20 lang=golang
 *
 * [20] 有效的括号
 */

// @lc code=start
func isValid(s string) bool {
	// 简单使用栈的思想
	// 1. 遇到左括号，入栈
	// 2. 遇到右括号，出栈
	// 3. 最后栈为空，说明括号有效

	// 1. 初始化栈
	stack := []byte{}
	// 2. 遍历字符串
	for i := 0; i < len(s); i++ {
		// 3. 如果是左括号，入栈
		if s[i] == '(' || s[i] == '[' || s[i] == '{' {
			stack = append(stack, s[i])
			continue
		}
		// 4. 如果是右括号，出栈
		if len(stack) == 0 {
			return false
		}
		c := stack[len(stack)-1]
		stack = stack[:len(stack)-1]

		// 5. 判断是否匹配
		if s[i] == ')' && c != '(' {
			return false
		}
		if s[i] == ']' && c != '[' {
			return false
		}
		if s[i] == '}' && c != '{' {
			return false
		}
	}

	// 6. 栈为空，说明括号有效
	return len(stack) == 0
}

// @lc code=end