Find the validity of an input string s that only contains the letters '(', ')' and '*'.
A string entered is legitimate if
Input : s = (*))
Output : true
Explanation : The * can be replaced by an opening '(' bracket. The string after replacing the * mark is "(())" and is a valid string.
Input : s = *(()
Output : false
Explanation : The * replaced with any bracket does not form a valid string.
Input : s = (**()))
The problem is to check if a given string containing parentheses and asterisks can be considered a valid parenthesis string. A string is valid if each opening parenthesis has a corresponding closing parenthesis and they appear in the correct order. The asterisk can be replaced with an opening parenthesis, a closing parenthesis, or an empty character, adding complexity to the problem.
To solve the problem, imagine a simpler scenario without asterisks where the task is to validate a string of only parentheses. Using a counter to track the balance between opening and closing parentheses helps determine validity. Introducing asterisks requires considering all possible replacements for each asterisk. Recursion is an effective method to explore all combinations by treating each asterisk as three separate branches: an opening parenthesis, a closing parenthesis, and an empty character. This brute force approach will check all possible strings generated by these replacements.
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
/* Helper function to recursively check
if the string is valid or not */
bool checkValid(int ind, int count, string &s,
vector<vector<int>> &dp){
// Base case
if(count < 0) return false;
// Base case
if(ind == s.size()) {
return (count == 0);
}
// If already computed, return the value directly
if(dp[ind][count] != -1) return dp[ind][count];
bool ans = false;
// If the current index has '('
if(s[ind] == '(')
ans = checkValid(ind+1, count+1, s, dp);
// If the current index has ')'
else if(s[ind] == ')')
ans = checkValid(ind+1, count-1, s, dp);
// else if the current index has '*'
else {
for(int i=-1; i <= 1; i++) {
ans = ans || checkValid(ind+1, count + i, s, dp);
}
}
// Store the value in DP and return the value
return dp[ind][count] = ans;
}
public:
// Function to check if the given string is valid
bool isValid(string s) {
int n = s.size();
// DP table
vector<vector<int>> dp(n, vector<int>(n, -1));
return checkValid(0, 0, s, dp);
}
};
int main() {
string s = "(*))";
/* Creating an instance of
Solution class */
Solution sol;
/* Function call to get the single
number in the given array */
int ans = sol.isValid(s);
if(ans)
cout << "The given string is valid.";
else
cout << "The given string is not valid";
return 0;
}import java.util.Arrays;
class Solution {
/* Helper function to recursively check
if the string is valid or not */
private boolean checkValid(int ind, int count, String s, int[][] dp) {
// Base case
if (count < 0) return false;
// Base case
if (ind == s.length()) {
return (count == 0);
}
// If already computed, return the value directly
if (dp[ind][count] != -1) return dp[ind][count] == 1;
boolean ans = false;
// If the current index has '('
if (s.charAt(ind) == '(')
ans = checkValid(ind + 1, count + 1, s, dp);
// If the current index has ')'
else if (s.charAt(ind) == ')')
ans = checkValid(ind + 1, count - 1, s, dp);
// else if the current index has '*'
else {
for (int i = -1; i <= 1; i++) {
ans = ans || checkValid(ind + 1, count + i, s, dp);
}
}
// Store the value in DP and return the value
dp[ind][count] = ans ? 1 : 0;
return ans;
}
// Function to check if the given string is valid
public boolean isValid(String s) {
int n = s.length();
// DP table
int[][] dp = new int[n][n];
for (int[] row : dp) {
Arrays.fill(row, -1);
}
return checkValid(0, 0, s, dp);
}
}
class Main {
public static void main(String[] args) {
String s = "(*))";
/* Creating an instance of
Solution class */
Solution sol = new Solution();
/* Function call to check if the string
is valid */
boolean ans = sol.isValid(s);
if (ans)
System.out.println("The given string is valid.");
else
System.out.println("The given string is not valid.");
}
}class Solution:
# Helper function to recursively check
# if the string is valid or not
def checkValid(self, ind, count, s, dp):
# Base case
if count < 0: return False
# Base case
if ind == len(s):
return count == 0
# If already computed, return the value directly
if dp[ind][count] != -1: return dp[ind][count]
ans = False
# If the current index has '('
if s[ind] == '(':
ans = self.checkValid(ind+1, count+1, s, dp)
# If the current index has ')'
elif s[ind] == ')':
ans = self.checkValid(ind+1, count-1, s, dp)
# else if the current index has '*'
else:
for i in range(-1, 2):
ans = ans or self.checkValid(ind+1, count+i, s, dp)
# Store the value in DP and return the value
dp[ind][count] = ans
return ans
# Function to check if the given string is valid
def isValid(self, s):
n = len(s)
# DP table
dp = [[-1] * n for _ in range(n)]
return self.checkValid(0, 0, s, dp)
# Driver Code
if __name__ == "__main__":
s = "(*))"
# Creating an instance of Solution class
sol = Solution()
# Function call to check if the string is valid
ans = sol.isValid(s)
if ans:
print("The given string is valid.")
else:
print("The given string is not valid.")class Solution {
/* Helper function to recursively check
if the string is valid or not */
checkValid(ind, count, s, dp) {
// Base case
if (count < 0) return false;
// Base case
if (ind == s.length) {
return (count == 0);
}
// If already computed, return the value directly
if (dp[ind][count] !== -1) return dp[ind][count];
let ans = false;
// If the current index has '('
if (s[ind] === '(')
ans = this.checkValid(ind + 1, count + 1, s, dp);
// If the current index has ')'
else if (s[ind] === ')')
ans = this.checkValid(ind + 1, count - 1, s, dp);
// else if the current index has '*'
else {
for (let i = -1; i <= 1; i++) {
ans = ans || this.checkValid(ind + 1, count + i, s, dp);
}
}
// Store the value in DP and return the value
dp[ind][count] = ans;
return ans;
}
// Function to check if the given string is valid
isValid(s) {
let n = s.length;
// DP table
let dp = Array.from({ length: n }, () => Array(n).fill(-1));
return this.checkValid(0, 0, s, dp);
}
}
// Driver Code
const s = "(*))";
// Creating an instance of Solution class
const sol = new Solution();
// Function call to check if the string is valid
const ans = sol.isValid(s);
if (ans)
console.log("The given string is valid.");
else
console.log("The given string is not valid.");Time Complexity O(3n) : This is because, in the worst case, the function makes three recursive calls for each step, leading to an exponential growth of the number of calls.
Space Complexity O(n) :This is due to the space used by the recursion stack, which can go up to the depth of the input size n.
The optimal approach builds on the idea of balancing opening and closing parentheses but introduces a method to efficiently handle asterisks. By maintaining a range of possible balances (minimum and maximum count of open parentheses), the solution tracks the potential valid states as the string is processed. This range ensures that all valid configurations are considered without explicitly generating each possible string.
Instead of treating each asterisk as three separate branches in a recursion tree, maintain two variables representing the minimum and maximum possible number of open parentheses. As each character in the string is processed, update these variables accordingly. If an asterisk is encountered, adjust the range to reflect its three possible replacements. Throughout the process, ensure that the minimum number of open parentheses never goes negative. At the end of the string, check if the minimum count is zero to determine validity.
#include <iostream>
#include <string>
using namespace std;
class Solution {
public:
bool isValid(string s) {
int minOpen = 0, maxOpen = 0;
for (char c : s) {
if (c == '(') {
minOpen++; // Treat as opening
maxOpen++; // Treat as opening
} else if (c == ')') {
minOpen--; // Treat as closing
maxOpen--; // Treat as closing
} else if (c == '*') {
minOpen--; // Treat as closing
maxOpen++; // Treat as opening
}
if (maxOpen < 0) return false; // More closing parentheses than opening
if (minOpen < 0) minOpen = 0; // Reset minOpen if negative
}
return minOpen == 0; // Check if balanced
}
};
int main() {
Solution sol;
string s = "(({}))";
cout << (sol.isValid(s) ? "true" : "false") << endl;
return 0;
}
class Solution {
public boolean isValid(String s) {
int minOpen = 0, maxOpen = 0;
for (char c : s.toCharArray()) {
if (c == '(') {
minOpen++; // Treat as opening
maxOpen++; // Treat as opening
} else if (c == ')') {
minOpen--; // Treat as closing
maxOpen--; // Treat as closing
} else if (c == '*') {
minOpen--; // Treat as closing
maxOpen++; // Treat as opening
}
if (maxOpen < 0) return false; // More closing parentheses than opening
if (minOpen < 0) minOpen = 0; // Reset minOpen if negative
}
return minOpen == 0; // Check if balanced
}
public static void main(String[] args) {
Solution sol = new Solution();
String s = "(({}))";
System.out.println(sol.isValid(s) ? "true" : "false");
}
}
class Solution(object):
def isValid(self, s):
minOpen, maxOpen = 0, 0
for c in s:
if c == '(':
minOpen += 1 # Treat as opening
maxOpen += 1 # Treat as opening
elif c == ')':
minOpen -= 1 # Treat as closing
maxOpen -= 1 # Treat as closing
elif c == '*':
minOpen -= 1 # Treat as closing
maxOpen += 1 # Treat as opening
if maxOpen < 0:
return False # More closing parentheses than opening
if minOpen < 0:
minOpen = 0 # Reset minOpen if negative
return minOpen == 0 # Check if balanced
if __name__ == "__main__":
sol = Solution()
s = "(({}))"
print("true" if sol.isValid(s) else "false")
class Solution {
isValid(s) {
let minOpen = 0, maxOpen = 0;
for (let c of s) {
if (c === '(') {
minOpen++; // Treat as opening
maxOpen++; // Treat as opening
} else if (c === ')') {
minOpen--; // Treat as closing
maxOpen--; // Treat as closing
} else if (c === '*') {
minOpen--; // Treat as closing
maxOpen++; // Treat as opening
}
if (maxOpen < 0) return false; // More closing parentheses than opening
if (minOpen < 0) minOpen = 0; // Reset minOpen if negative
}
return minOpen === 0; // Check if balanced
}
}
// Main method for testing
const sol = new Solution();
const s = "(({}))";
console.log(sol.isValid(s) ? "true" : "false");
Time Complexity O(N) : This is because the algorithm processes each element of the input exactly once, leading to a linear time complexity.
Space Complexity O(1) : This is due to the use of a constant amount of extra space regardless of the input size, making the space complexity constant.
Q: How does low and high handle the flexibility of *?
A: low assumes the * acts as a right parenthesis ) or empty string "", minimizing unmatched left parentheses. high assumes the * acts as a left parenthesis (, maximizing unmatched left parentheses. Together, they ensure all possible interpretations of * are covered.
Q: What if the string contains no ( or )?
A: If the string contains only *, it is always valid since all * can be treated as empty strings.
Q: What if * had additional roles or constraints?
A: Modify the logic to handle new constraints. For example, if * could represent multiple parentheses, you might need a more complex simulation or stack-based approach.
Q: How does this approach compare to using a stack?
A: A stack-based approach keeps track of potential matches directly but is less space-efficient (O(n)). The two-counter method is more efficient (O(1) space) and simpler for this problem.