Sponsored
Sponsored
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.
1function isValid(s) {
2 const stack = [];
3 const map = {
4 ')': '(',
5 '}': '{',
6 ']': '['
7 };
8 for (const char of s) {
9 if (map[char]) {
10 if (stack.pop() !== map[char]) {
11 return false;
12 }
13 } else {
14 stack.push(char);
15 }
16 }
17 return stack.length === 0;
18}
19
20console.log(isValid("()[]{}")); // Output: true
21console.log(isValid("(]")); // Output: falseThe JavaScript solution uses an array as a stack for keeping track of open brackets and a map to match them with closing brackets, ensuring a valid structure of the input string.
In Java, using StringBuilder along with character matching achieves similar stack manipulation while maintaining easy removability and appendability onto the existing stack representation.