Sponsored
Sponsored
In this approach, we use two stacks. One stack will store indices of '(' characters, and the other will store indices of '*' characters as we traverse the string.
If we find a ')' character and there are unmatched '(' in the stack, we pop one out as it can be matched. If no '(' is available, we match using '*'. After processing, all unmatched '(' should be balanced by '*' appearing after them in the string.
Time Complexity: O(n), as we process each character of the string once.
Space Complexity: O(n), due to use of two stacks to track indices of '(' and '*'.
1def checkValidString(s):
2 open_stack = []
3 star_stack = []
4 for i, char in enumerate(s):
5 if char == '(':
6 open_stack.append(i)
7 elif char == '*':
8 star_stack.append(i)
9 else:
10 if open_stack:
11 open_stack.pop()
12 elif star_stack:
13 star_stack.pop()
14 else:
15 return False
16 while open_stack and star_stack:
17 if open_stack.pop() > star_stack.pop():
18 return False
19 return not open_stackThe function uses two stacks to keep track of the positions of '(' and '*' characters. When encountering ')', it attempts to match it using an available '(' or '*'. After scanning the string, any remaining unmatched '(' is checked against '*' to ensure validity.
This approach involves maintaining two balance counts: one for keeping a minimal balance and the other for maximal considering '*' as both '(' and ')'.
As we traverse, the minimal balance ensures ')' never exceeds '(' without the aid of '*', while the maximal balance accounts for replacing '*' with '('. If at any point the maximal balance is negative, then parentheses can't be balanced.
Time Complexity: O(n), as we traverse the string once.
Space Complexity: O(1), since we use a constant amount of extra space regardless of the input size.
1#include <string>
2using namespace std;
3
4bool checkValidString(string s) {
5 int minBal = 0, maxBal = 0;
for (char c : s) {
if (c == '(') {
minBal++;
maxBal++;
} else if (c == ')') {
minBal--;
maxBal--;
} else {
minBal--;
maxBal++;
}
if (maxBal < 0) return false;
if (minBal < 0) minBal = 0;
}
return minBal == 0;
}The C++ solution uses two balance counters. It iterates over the string adjusting minBal and maxBal based on the character encountered ('(', ')', or '*'). The maxBal ensures we never have more ')' than possible '('. Negative minBal is reset to reflect reality where '*' can become '(' or empty.