20 Valid Parentheses

Problem Statement

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.

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

Approach

We init a hashmap for our pairs. Next we handle the base conditions to return early. We then init a stack that keeps track of opening parentheses. If it is not an opened one we pop the top of the stack and evaluate the current closing parentheses, return false if no match.
In the end the stack should be empty.

Solution

const pairs = {
"(": ")",
"[": "]",
"{": "}"
}

var isValid = function(s) {
	if (s.length % 2 === 1) return false
	if (s[0] === "]" || s[0] === ")" || s[0] === "}") return false
	if (s[s.length - 1] === "[" || s[s.length - 1] === "(" || s[s.length - 1] === "{") return false
	
	let stack = []

for (let i=0; i<s.length; i++) {
	// if it's an opening bracket, push into stack
	// else, assume it's closing bracket and check if it matches anything
	if(s[i] === "[" || s[i] === "(" || s[i] === "{") {
		stack.push(s[i])
	} else if (pairs[stack.pop()] !== s[i]) {
		return false
	}
}

return stack.length === 0
};

Questions

1. How do we know that we need a stack?
   Stack is great for nested structures or matching pairs as it keeps track of the opening brackets encountered so far.
2. How do we check for an opening bracket when we encounter a closing bracket?
   Use the hashmap created

References

LC

Related

DSA MOC