20. Valid Parentheses

Prompt

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.

Examples

• Example 1:
  • Input: s = ”()”
  • Output: true
• Example 2:
  • Input: s = ”()[]{}”
  • Output: true
• Example 3:
  • Input: s = ”(]”
  • Output: false
• Example 4:
  • Input: s = ”([])”
  • Output: true
• Example 5:
  • Input: s = ”([)]”
  • Output: false

Solution

In C++

bool isOpening(char c) {
	return string("([{").find(c) != string::npos;
}
bool isClosing(char c) {
	return string(")]}").find(c) != string::npos;
}
bool matchesTop(char c, char top) {
	switch (c) {
	case ')':
		return top == '(';
		break;
	case '}':
		return top == '{';
		break;
	case ']':
		return top == '[';
		break;
	}
	return false;
}
 
bool isValid(string s) {
	stack<char> stack;
	for (char c : s) {
		if (isOpening(c)) stack.push(c);
		else if (isClosing(c)) {
			if (stack.empty() ||
				!matchesTop(c, stack.top())) return false;
			else stack.pop();
		}
	}
	return stack.size() == 0;
}

Explanation

Using a stack, add opening paren to the top. The string is valid if as we remove the top when we encounter the corresponding closing paren, the stack ends with size zero, indicating that all opening paren were closed.

Big O Analysis

Time Complexity

The time complexity is $O(n)$

Auxiliary Space Complexity

The space complexity is $O(n)$