Valid Parentheses

Easy

The problem

Given a string s made only of the bracket characters ( ) [ ] { }, return true if every bracket is closed by the matching kind of bracket, in the correct order. Otherwise return false.

Example 1
Input: s = "{[()]}"
Output: true
Each bracket is closed by its partner, and the inner ones are closed before the outer ones.
Example 2
Input: s = "(]"
Output: false
The ( is closed by a ] which is the wrong kind.
Example 3
Input: s = "(()"
Output: false
One ( is never closed.

Limits

1 ≤ s.length ≤ 100,000
s contains only the characters ()[]{}

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

The most recently opened bracket must be the first one closed.

The idea

Push every opening bracket; on a closing bracket the top of the stack must be its partner (pop it). The stack must be empty at the end.

Target: O(n) time, O(n) space

Go function shape

func isValid(s string) bool

Reference solution

Tested with go test. Try it yourself first, then compare.

// IsValid: are all brackets closed by the right type, in the right order?
func IsValid(s string) bool {
	pairs := map[byte]byte{')': '(', ']': '[', '}': '{'}
	stack := []byte{}
	for i := 0; i < len(s); i++ {
		c := s[i]
		if open, isClose := pairs[c]; isClose {
			if len(stack) == 0 || stack[len(stack)-1] != open {
				return false
			}
			stack = stack[:len(stack)-1]
		} else {
			stack = append(stack, c)
		}
	}
	return len(stack) == 0 // leftovers are unclosed brackets
}

Read the lesson: Stack Basics