20. Valid Parentheses

题目 #

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

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.
  3. Every close bracket has a corresponding open bracket of the same type.   Example 1:
Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

Constraints:

  • $1 <= s.length <= 10^4$
  • s consists of parentheses only ‘()[]{}’.

思路1 #

分析 #

  • 没啥说的，栈搞定就好

代码 # 

 1func isValid(s string) bool {
 2	n := len(s)
 3	if n%2 == 1 {
 4		return false
 5	}
 6
 7	check := map[byte]byte{
 8		')': '(',
 9		']': '[',
10		'}': '{',
11	}
12	stack := make([]byte, 0, 1)
13	for _, v := range s {
14		if t := check[byte(v)]; t > 0 {
15			if len(stack) == 0 || t != stack[len(stack)-1] {
16				return false
17			}
18			stack = stack[:len(stack)-1]
19		} else {
20			stack = append(stack, byte(v))
21		}
22	}
23	return len(stack) == 0
24}