**Explanation**

The point to this question is to use a stack data structure to keep track of string validity. We want to iterate through string *s* one character at a time, while considering the following 2 cases:

- The character is an opening bracket - push onto stack regardless what type.
- The character is a closing bracket - pop element off stack, if possible, and check whether it matches the given character. Return false if stack is empty or if they don't match.

At the end, return true if the stack is empty, meaning all brackets matched; return false if non-empty.

**Time Complexity**

The time complexity is O(n) where n is the length of input *s*, since we iterate through each character once.

```
class Solution {
public boolean isOpening(char c) {
return c == '{' || c == '(' || c == '[';
}
public boolean areMatching(char a, char b) {
return a == '{' && b == '}' ||
a == '(' && b == ')' ||
a == '[' && b == ']';
}
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// Case 1: Opening bracket
if (isOpening(c)) {
stack.push(c);
}
// Case 2: Closing bracket
else {
if (stack.isEmpty()) return false;
char bracket = stack.pop();
if (!areMatching(bracket, c)) {
return false;
}
}
}
return stack.isEmpty();
}
}
```