leetcode 20. 有效的括号

目录

• 一、题目
• • 有效的括号
• 二、解题思路
• • 思路一：堆栈
  • 思路二：整对删除
• 三、代码实现
• • 解法一：堆栈
  • 解法二：整对删除

---

一、题目 有效的括号

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

有效字符串需满足：

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

示例 1：

输入：s = “()”
输出：true

示例 2：

输入：s = “()[]{}”
输出：true

示例 3：

输入：s = “(]”
输出：false

示例 4：

输入：s = “([)]”
输出：false

示例 5：

输入：s = “{[]}”
输出：true

二、解题思路 思路一：堆栈

题目比较简单，很容易想到使用堆栈来解决该问题

1. 将括号进行分类，分为左括号和右括号：‘{’、‘[’、‘(‘均为左括号，’}’、‘]’、')'为右括号
2. 遍历字符串，如果为左括号，存入堆栈；如果为右括号，判断栈顶元素是否和该右括号匹配。此处匹配可以利用map来实现，示例如下：

	validMap := map[byte]byte{
		'}': '{',
		']': '[',
		')': '(',
	}
	此处将右括号定义为key，左括号定义为value的目的是：
	在判断字符为右括号的同时直接将其对应的左括号取出，方便后续和栈顶元素进行匹配

3. 如果不匹配直接返回false，表示该字符串无效；如果匹配则将栈顶元素移除
4. 遍历完成后，校验该栈是否为空，不为空表示还有元素未出栈，字符串无效

思路二：整对删除

此实现方法为一种取巧的思路，具体思路为：

将’(‘，’)’ 和 ‘{’，‘}’ 和 ‘[’，‘]’ 成对的进行删除，直到无法继续删除，最后判断字符串是否还有剩余，如有则表示该字符串无效

三、代码实现 解法一：堆栈

golang代码实现

func IsValid(s string) bool {
	if len(s)%2 != 0 {
		// 如果s长度不为2的倍数，该字符串一定无效
		return false
	}
	validMap := map[byte]byte{
		'}': '{',
		']': '[',
		')': '(',
	}
	stack := make([]byte, 0)
	for _, char := range s {
		if v, ok := validMap[byte(char)]; ok {
			// 如果当前字符为右括号，则需要判断堆栈栈顶的字符是否为对应的左括号
			if len(stack) < 1 || stack[len(stack)-1] != v {
				// 栈顶元素和预期左括号不相等则字符串不合规
				return false
			}
			// 如果匹配成功则移除栈顶元素
			stack = stack[:len(stack)-1]
		} else {
			// 如果当前字符为左括号，将字符入栈
			stack = append(stack, byte(char))
		}
	}

	return len(stack) == 0
}

解题效果：

解法二：整对删除

golang代码实现

func isValid(s string) bool {
    loop := true
	for loop {
		trim := strings.ReplaceAll(s, "{}", "")
		trim = strings.ReplaceAll(trim, "[]", "")
		trim = strings.ReplaceAll(trim, "()", "")
		loop = len(trim) != len(s)
		s = trim
	}
	return len(s) == 0
}

解题效果：