This approach uses a stack to efficiently match opening and closing brackets. The stack stores opening brackets, and for each closing bracket encountered, it checks if it closes the last opened bracket (top of the stack).
Time Complexity: O(n), where n is the length of the string, since we process each character once.
Space Complexity: O(n) in the worst case if the string consists only of opening brackets.
1import java.util.Stack;
2
3public class Solution {
4 public boolean isValid(String s) {
5 Stack<Character> stack = new Stack<>();
6 for (char c : s.toCharArray()) {
7 if (c == '(' || c == '{' || c == '[') {
8 stack.push(c);
9 } else {
10 if (stack.isEmpty()) return false;
11 char top = stack.pop();
12 if ((c == ')' && top != '(') ||
13 (c == '}' && top != '{') ||
14 (c == ']' && top != '['))
15 return false;
16 }
17 }
18 return stack.isEmpty();
19 }
20}The Java solution employs a stack to process and match each bracket in the string. If there's any imbalance or mismatched pair, it returns false.
This approach uses two pointers with stack-like behavior internally, taking advantage of simple list operations for push and pop.
Time Complexity: O(n)
Space Complexity: O(n/2) = O(n)
1#include <stdbool.h>
2#include <stdio.h>
3#include <string.h>
4
5bool isValid(char * s) {
6 int len = strlen(s);
7 if (len % 2 != 0) return false;
8
9 char stack[len / 2];
10 int top = -1;
11
12 for (int i = 0; s[i]; i++) {
13 switch (s[i]) {
14 case '(': case '{': case '[':
15 if (top == len / 2 - 1) return false;
16 stack[++top] = s[i];
17 break;
18 case ')':
19 if (top == -1 || stack[top--] != '(') return false;
20 break;
21 case '}':
22 if (top == -1 || stack[top--] != '{') return false;
23 break;
24 case ']':
25 if (top == -1 || stack[top--] != '[') return false;
26 break;
27 }
28 }
29
30 return top == -1;
31}This C solution strategically checks potential stack overflow and underflow using an array pointer technique, relying on an indexing control within the allowed stack-size limits. Each mismatched pair check ensures parentheses are properly closed.