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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public bool IsValid(string s) {
6 Stack<char> stack = new Stack<char>();
7 foreach (char c in s) {
8 if (c == '(' || c == '{' || c == '[') {
9 stack.Push(c);
10 } else {
11 if (stack.Count == 0) return false;
12 char top = stack.Pop();
13 if ((c == ')' && top != '(') ||
14 (c == '}' && top != '{') ||
15 (c == ']' && top != '['))
16 return false;
17 }
18 }
19 return stack.Count == 0;
20 }
21}
22
23public class Program {
24 public static void Main() {
25 var solution = new Solution();
26 Console.WriteLine(solution.IsValid("()[]{}")); // Output: True
27 Console.WriteLine(solution.IsValid("(]")); // Output: False
28 }
29}The C# solution uses a stack to evaluate valid sequences of parentheses, brackets, and braces. The use of a stack simplifies checking against preceding open brackets.
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)
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public bool IsValid(string s) {
6 if (s.Length % 2 != 0) return false;
7
8 var stack = new List<char>();
9 foreach (char c in s) {
10 if (c == '(' || c == '{' || c == '[') {
11 stack.Add(c);
12 } else {
13 if (stack.Count == 0) return false;
14 char top = stack[stack.Count - 1];
15 stack.RemoveAt(stack.Count - 1);
16 if ((c == ')' && top != '(') ||
17 (c == '}' && top != '{') ||
18 (c == ']' && top != '['))
19 return false;
20 }
21 }
22 return stack.Count == 0;
23 }
24}
25
26public class Program {
27 public static void Main() {
28 var solution = new Solution();
29 Console.WriteLine(solution.IsValid("()[]{}")); // Output: True
30 Console.WriteLine(solution.IsValid("(]")); // Output: False
31 }
32}The C# solution capitalizes on List operations like Add and RemoveAt, imitating stack-like behavior without the conventional stack class, enabling fluid manipulation on a character basis.