Questions

Given a string s 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.

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

Implementation: ValidParens

As we encounter a closing bracket, the whole string is valid iff there was an open bracket of the same type that came before it. Now, since there can be nested brackets like (((()))), we need to somehow keep track of the order these open brackets appeared. However, the order if accessing them is opposite (to the order of writing them). Thus, a stack could be used here.

So the algorithm is:

1. When we encounter an open bracket, we put it in the stack.
2. When we encounter a closing bracket, we check the stack for: 2.1 if the top element is of different type, the string is invalid. 2.2 if there are no elements in the stack, the string is invalid.
3. Otherwise, we move on.
4. An edge condition could be if there's only open brackets, so at the end we should check if the stack size is 0. If not, the string is invalid.

Time complexity

O(n)

Space complexity

O(n)

Return to Index