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.
1public bool CheckValidString(string s) {
2 int minBal = 0, maxBal = 0;
3 foreach (char c in s) {
4 if (c == '(') {
5 minBal++;
maxBal++;
} else if (c == ')') {
minBal--;
maxBal--;
} else {
minBal--;
maxBal++;
}
if (maxBal < 0) return false;
if (minBal < 0) minBal = 0;
}
return minBal == 0;
}Similar to the C++ approach, this C# solution uses two counters, minBal and maxBal, to track possible balances while iterating over the string. The checks for negative maxBal ensure backwards checking validity, and minBal is corrected to reflect legal '*'.