An input string is valid if:
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:
O(n)
O(n)