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.
1#include <stdbool.h>
2#include <stdio.h>
3#include <string.h>
4
5bool isValid(char * s) {
6 char stack[strlen(s)];
7 int top = -1;
8 for (int i = 0; s[i]; i++) {
9 char c = s[i];
10 if (c == '(' || c == '{' || c == '[') {
11 stack[++top] = c;
12 } else {
13 if (top == -1) return false;
14 char topChar = stack[top--];
15 if ((c == ')' && topChar != '(') ||
16 (c == '}' && topChar != '{') ||
17 (c == ']' && topChar != '['))
18 return false;
19 }
20 }
21 return top == -1;
22}
23
24int main() {
25 printf("%d\n", isValid("()[]{}")); // Output: 1 (true)
26 printf("%d\n", isValid("(]")); // Output: 0 (false)
27 return 0;
28}This C program uses an array stack to store opening brackets. It checks each character from left to right, pushing opening brackets onto the stack and popping it to match with corresponding closing brackets. If a mismatch is found or the stack isn't empty at the end, 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)
1public class Solution {
2 public boolean isValid(String s) {
3 if (s.length() % 2 != 0) return false;
4
5 StringBuilder stack = new StringBuilder();
6 for (char c : s.toCharArray()) {
7 if (c == '(' || c == '{' || c == '[') {
8 stack.append(c);
9 } else {
10 int length = stack.length();
11 if (length == 0) return false;
12 char top = stack.charAt(length - 1);
13 stack.deleteCharAt(length - 1);
14 if ((c == ')' && top != '(') ||
15 (c == '}' && top != '{') ||
16 (c == ']' && top != '['))
17 return false;
18 }
19 }
20 return stack.length() == 0;
21 }
22}In Java, using StringBuilder along with character matching achieves similar stack manipulation while maintaining easy removability and appendability onto the existing stack representation.