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.
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.