In the valid parenthesis string problem we have given a string containing ‘(‘, ‘)‘ and ‘*‘, check if the string is balanced if ‘*‘ can be replaced with ‘(‘, ‘)‘ or an empty string.
Table of Contents
Examples
Input
“()”
Output
true
Input
“*)”
Output
true
Input
“(*))”
Output
true
Naive Approach for Valid Parenthesis String
‘*‘ can take three possible values, try all these values, if there is any valid balanced string, then the current string is valid.
- Traverse the given string.
- Recursively replace ‘*‘ with ‘(‘, ‘)‘ and empty string.
- If any combination is a balanced string, then the given string is balanced.
Consider an example, “*)”,
JAVA Code for Valid Parenthesis String
public class ValidParanthesisString {
private static boolean ans;
private static boolean isValid(String str) {
// Initialise ans as false
ans = false;
// Recur and try all the combinations possible for the string
recurStr(new StringBuilder(str), 0);
return ans;
}
private static void recurStr(StringBuilder str, int i) {
if (i == str.length()) {
// check validity of the string, as it is fully formed when i = str.length()
ans |= checkValidity(str);
} else if (str.charAt(i) == '*') {
// Replace * with (
str.setCharAt(i, '(');
recurStr(str, i + 1);
// Replace * with )
str.setCharAt(i, ')');
recurStr(str, i + 1);
// replace * with empty string
str.setCharAt(i, ' ');
recurStr(str, i + 1);
} else {
// If the current character is not * continue for next character
recurStr(str, i + 1);
}
}
// Function to check if given string is balanced or not
private static boolean checkValidity(StringBuilder str) {
int bal = 0;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '(') {
bal++;
} else if (str.charAt(i) == ')') {
bal--;
}
if (bal < 0) {
break;
}
}
return bal == 0;
}
public static void main(String[] args) {
// Example 1
String str = "()";
System.out.println(isValid(str));
// Example 2
str = "(*)";
System.out.println(isValid(str));
// Example 3
str = "(*))";
System.out.println(isValid(str));
}
}C++ Code for Valid Parenthesis String
#include <iostream>
using namespace std;
bool ans;
// Function to check if given string is balanced or not
bool checkValidity(string str) {
int bal = 0;
for (int i = 0; i < str.size(); i++) {
if (str[i] == '(') {
bal++;
} else if (str[i] == ')') {
bal--;
}
if (bal < 0)
break;
}
return (bal == 0);
}
void recurStr(string str, int i) {
if (i == str.size()) {
// check validity of the string, as it is fully formed when i = str.length()
ans |= checkValidity(str);
} else if (str[i] == '*') {
// Replace * with (
str[i] = '(';
recurStr(str, i + 1);
// Replace * with )
str[i] = ')';
recurStr(str, i + 1);
// replace * with empty string
str[i] = ' ';
recurStr(str, i + 1);
} else {
// If the current character is not * continue for next character
recurStr(str, i + 1);
}
}
bool isValid(string str) {
// Initialise ans as false
ans = false;
// Recur and try all the combinations possible for the string
recurStr(str, 0);
return ans;
}
int main() {
string str = "()";
if (isValid(str)) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
// Example 2
str = "(*)";
if (isValid(str)) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
// Example 3
str = "(*))";
if (isValid(str)) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
return 0;
}true true true
Complexity Analysis
Time Complexity = O(n * 3n)
Space Complexity = O(3n), due to recursion
where n is the number of characters in the given string.
Optimal Approach for Valid Parenthesis String
For each character of the given string count the minimum and a maximum number of open brackets till this point.
- An open bracket increases the minimum and maximum value by 1.
- A close bracket decreases the minimum and maximum value by 1, lower value cannot be negative.
- An asterisk(*) decreases the minimum value by 1 and increases the maximum value by 1.
- If the maximum value becomes negative at any point, then the string is not balanced.
If the lower value of open brackets is 0, then the string is valid.
Example
Consider the string “(***)“,
- ‘(‘ : Increases minimum and maximum by 1{Index 0} (minimum = 1, maximum = 1)
- ‘*’ : Decreases minimum by 1 and increases maximum by 1 {Index 1, 2 and 3} (minimum = 0 and maximum = 4)
- ‘) : Decreases minimum and maximum by 1{Index 4} (minimum = 0 and maximum = 3)
minimum is 0 at the end of traversing, so the string is valid.
JAVA Code
public class ValidParanthesisString {
private static boolean isValid(String str) {
// Initialise minimum and maximum as 0
int minimum = 0, maximum = 0;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '(') {
// Open bracket increases minimum and maximum by 1
minimum++;
maximum++;
} else if (str.charAt(i) == ')') {
// Close bracket decreases minimum and maximum by 1
minimum--;
maximum--;
} else {
// asterisk(*) decreases minimum by 1 and increases maximum by 1
minimum--;
maximum++;
}
// If maximum becomes less than 0, string is not balanced
if (maximum < 0)
return false;
// minimum cannot be less than 0
minimum = Math.max(minimum, 0);
}
// If minimum is 0, then string is balanced
return minimum == 0;
}
public static void main(String[] args) {
// Example 1
String str = "()";
System.out.println(isValid(str));
// Example 2
str = "(*)";
System.out.println(isValid(str));
// Example 3
str = "(*))";
System.out.println(isValid(str));
}
}C++ Code
#include <iostream>
using namespace std;
bool isValid(string str) {
// Initialise minimum and maximum as 0
int minimum = 0, maximum = 0;
for (int i = 0; i < str.size(); i++) {
if (str[i] == '(') {
// Open bracket increases minimum and maximum by 1
minimum++;
maximum++;
} else if (str[i] == ')') {
// Close bracket decreases minimum and maximum by 1
minimum--;
maximum--;
} else {
// asterisk(*) decreases minimum by 1 and increases maximum by 1
minimum--;
maximum++;
}
// If maximum becomes less than 0, string is not balanced
if (maximum < 0)
return false;
// minimum cannot be less than 0
minimum = std::max(minimum, 0);
}
// If minimum is 0, then string is balanced
return (minimum == 0);
}
int main() {
string str = "()";
if (isValid(str)) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
// Example 2
str = "(*)";
if (isValid(str)) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
// Example 3
str = "(*))";
if (isValid(str)) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
return 0;
}true true true
Complexity Analysis for Valid Parenthesis String
Time Complexity = O(n)
Space Complexity = O(1)
where n is the number of characters in the given string.