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.
1def isValid(s: str) -> bool:
2 stack = []
3 mapping = {
4 ')': '(',
5 '}': '{',
6 ']': '['
7 }
8 for char in s:
9 if char in mapping:
10 top_element = stack.pop() if stack else '#'
11 if mapping[char] != top_element:
12 return False
13 else:
14 stack.append(char)
15 return not stackThis Python function utilizes a list as a stack to validate the parentheses. It features a dictionary to map closing to opening brackets, managing imbalance as it traverses the input.
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 <string>
2bool isValid(std::string s) {
3 if (s.size() % 2 != 0) return false;
4
5 std::string stack;
6 for (char& c : s) {
7 if (c == '(' || c == '{' || c == '[') {
8 stack.push_back(c);
9 } else {
10 if (stack.empty()) return false;
11 char top = stack.back();
12 stack.pop_back();
13 if ((c == ')' && top != '(') ||
14 (c == '}' && top != '{') ||
15 (c == ']' && top != '['))
16 return false;
17 }
18 }
19 return stack.empty();
20}The C++ solution here enhances string utilization with back() and pop_back() methods, forming a stack, but seeks to access in a controlled way without appending complex data structures.