20. Valid Parentheses

LeetCode 20. Valid Parentheses

Description

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

Tags

Stack, String

Solution

使用栈。遍历字符串，遇到任何左括号都将其入栈。如果遇到右括号，则检查栈顶是否是对应左括号，是则将该左括号弹出栈，否则返回false。最后如果栈为空则返回true，否则false。

Use a stack with capacity len(s)/2. Traverse the string. If the current character is one of three kinds of left parenthesis then push it into the stack. Otherwise, the current character should be one of three kinds of right parenthesis. Check if it is match with the left parenthesis on the top of the stack. Pop the stack if it is. If it is not or the stack is empty, return false. At last, return true only if the stack is empty.

Complexity

• Time complexity: $O(n)$

• Space complexity: $O(n)$

Code

func isValid(s string) bool {
	stack := make([]rune, 0, len(s)/2)
	for _, c := range s {
		switch c {
		case '(', '[', '{':
			stack = append(stack, c)
		case ')':
			if len(stack) > 0 && stack[len(stack)-1] == '(' {
				stack = stack[:len(stack)-1]
			} else {
				return false
			}
		case ']':
			if len(stack) > 0 && stack[len(stack)-1] == '[' {
				stack = stack[:len(stack)-1]
			} else {
				return false
			}
		case '}':
			if len(stack) > 0 && stack[len(stack)-1] == '{' {
				stack = stack[:len(stack)-1]
			} else {
				return false
			}
		}
	}
	return len(stack) == 0
}