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 '*'.
1function checkValidString(s) {
2 const openStack = [];
3 const starStack = [];
4 for (let i = 0; i < s.length; i++) {
5 if (s[i] === '(') {
6 openStack.push(i);
7 } else if (s[i] === '*') {
8 starStack.push(i);
9 } else {
10 if (openStack.length > 0) {
11 openStack.pop();
12 } else if (starStack.length > 0) {
13 starStack.pop();
14 } else {
15 return false;
16 }
17 }
18 }
19
20 while (openStack.length > 0 && starStack.length > 0) {
21 if (openStack.pop() > starStack.pop()) {
22 return false;
23 }
24 }
25
26 return openStack.length === 0;
27}The JavaScript solution follows the same logic as the Python one, utilizing arrays to emulate stacks. It matches ')' with '(' or '*', and at the end, checks if the remaining '(' can be matched with '*' that appears later in the string.
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 == '(') {
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 '*'.