0020. Valid Parentheses

20. Valid Parentheses #

题目 #

Given a string containing just the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Note that an empty string is also considered valid.

Example 1:


Input: "()"
Output: true

Example 2:


Input: "()[]{}"
Output: true

Example 3:


Input: "(]"
Output: false

Example 4:


Input: "([)]"
Output: false

Example 5:


Input: "{[]}"
Output: true

题目大意 #

括号匹配问题。

解题思路 #

遇到左括号就进栈push,遇到右括号并且栈顶为与之对应的左括号,就把栈顶元素出栈。最后看栈里面还有没有其他元素,如果为空,即匹配。

需要注意,空字符串是满足括号匹配的,即输出 true。

代码 #


package leetcode

func isValid(s string) bool {
	// 空字符串直接返回 true
	if len(s) == 0 {
		return true
	}
	stack := make([]rune, 0)
	for _, v := range s {
		if (v == '[') || (v == '(') || (v == '{') {
			stack = append(stack, v)
		} else if ((v == ']') && len(stack) > 0 && stack[len(stack)-1] == '[') ||
			((v == ')') && len(stack) > 0 && stack[len(stack)-1] == '(') ||
			((v == '}') && len(stack) > 0 && stack[len(stack)-1] == '{') {
			stack = stack[:len(stack)-1]
		} else {
			return false
		}
	}
	return len(stack) == 0
}



⬅️上一页

下一页➡️

Calendar Sep 6, 2020
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者