28 Sep 2023, 9:23 PM
28 Sep 2023, 9:23 PM

16. Valid Parentheses

#leetcode/20

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:

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

Solution

Solution in C++ using stack

This problem is the same as Alice and Bob's Game. We can use a stack to push a close bracket every time we see an open bracket. Thus, when we encounter a close bracket, we try to pop it. If we can't do it, because the stack is empty or the bracket in the stack doesn't match, we return false. Otherwise the bracket matched and we can pop it from the stack.

bool isValid(string s) {
	stack<int> stack;

	for (char c : s) {
		if (c == '(')
			stack.push(')');
		else if (c == '{')
			stack.push('}');
		else if (c == '[')
			stack.push(']');
		else if (stack.empty() || stack.top() != c)
			return false;
		else
			stack.pop();
	}
	return stack.empty();
}