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 <stack>
2#include <string>
3
4bool isValid(std::string s) {
5 std::stack<char> stack;
6 for (char& c : s) {
7 if (c == '(' || c == '{' || c == '[') {
8 stack.push(c);
9 } else {
10 if (stack.empty()) return false;
11 char top = stack.top();
12 stack.pop();
13 if ((c == ')' && top != '(') ||
14 (c == '}' && top != '{') ||
15 (c == ']' && top != '['))
16 return false;
17 }
18 }
19 return stack.empty();
20}In C++, we utilize the STL stack to handle opening brackets. It pushes each found opening bracket and checks them against closing ones as they appear. The program efficiently manages balance checking through stack operations.
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)
1function isValid(s) {
2 if (s.length % 2 !== 0) return false;
3
4 const stack = [];
5 for (let char of s) {
6 if (char === '(' || char === '{' || char === '[') {
7 stack.push(char);
8 } else {
9 if (stack.length === 0) return false;
10 const top = stack.pop();
11 if (!((char === ')' && top === '(') ||
12 (char === '}' && top === '{') ||
13 (char === ']' && top === '['))) {
14 return false;
15 }
16 }
17 }
18 return stack.length === 0;
19}
20
21console.log(isValid("()[]{}")); // Output: true
22console.log(isValid("(]")); // Output: falseThe JavaScript implementation checks for an even length initially, then processes each character with a conventional stack dynamics rooted in array handling - verifying the lock-and-key representation of valid parentheses.