Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
I thought of a O(n) solution:
If I encounter a closing parentesis, the only thing I must ensure is there
was an opening parentesis before. If not, the expression isn't valid. An opening
parentesis can be a star as well. Stars I don't use, don't matter, they are null.
This doesn't account for too many open parentesis. But If I reverse the problem, I can
do the same again and find out, if all opening parentesis actually match a closing or
a "*".
It passes all the test cases and a few more. But the prove isn't that easy. It would, if
I used a stack and change the '*' into the according parentesis, but I think it's not
necessary. Any thoughts?
#include <iostream>
#include <string>
using namespace std;
bool validExpression(const string& expression)
{
string expr(expression); // make a modifiable copy of expr uses withing auxilary func.
auto aux = [&expr]() -> bool {
int openCtr = 0;
int wildCtr = 0;
for (char& c : expr) {
if (c == '(') {
c = ')';
openCtr++;
} else if (c == ')') {
c = '(';
if (openCtr > 0) openCtr--; // match ')' to a '('
else if (wildCtr > 0) wildCtr--; // match ')' to a '*'
else return false; // can't match ')' to anyting, error
} else if (c == '*') {
wildCtr++;
}
}
reverse(expr.begin(), expr.end()); // reverse string
return true;
};
return aux() && aux();
}
int main()
{
cout << "TC1: " << (validExpression("(*)") == true) << endl;
cout << "TC2: " << (validExpression("((*)") == true) << endl;
cout << "TC3: " << (validExpression("((*))") == true) << endl;
cout << "TC4: " << (validExpression("((*)))") == true) << endl;
cout << "TC5: " << (validExpression("((*))))") == false) << endl;
cout << "TC6: " << (validExpression("*((*))))") == true) << endl;
cout << "TC7: " << (validExpression("(*((*))))") == true) << endl;
cout << "TC8: " << (validExpression("(*)(*)(**") == true) << endl;
cout << "TC9: " << (validExpression("(*)(*)(***") == true) << endl;
cout << "TC10: " << (validExpression("((*)(*)(***") == true) << endl;
cout << "TC11: " << (validExpression("(()(*)(") == false) << endl;
cout << "TC12: " << (validExpression("(()(*)(") == false) << endl;
cout << "TC13: " << (validExpression("****()))))") == true) << endl;
cout << "TC12: " << (validExpression("") == true) << endl;
cout << "TC13: " << (validExpression("()") == true) << endl;
cout << "TC14: " << (validExpression("(*)") == true) << endl;
cout << "TC15: " << (validExpression("(*)(*)") == true) << endl;
cout << "TC16: " << (validExpression("*") == true) << endl;
cout << "TC17: " << (validExpression("**") == true) << endl;
cout << "TC18: " << (validExpression("*)") == true) << endl;
cout << "TC19: " << (validExpression("*(((()())()))())") == true) << endl;
cout << "TC20: " << (validExpression("*()(") == false) << endl;
cout << "TC21: " << (validExpression("**()(") == false) << endl;
cout << "TC22: " << (validExpression("**(**)*(") == false) << endl;
cout << "TC23: " << (validExpression(")**") == false) << endl;
cout << "TC24: " << (validExpression("****()))))") == true) << endl;
cout << "TC25: " << (validExpression("****())))") == true) << endl;
cout << "TC26: " << (validExpression("****())))))") == false) << endl;
cout << "TC27: " << (validExpression("***********************(((((()") == false) << endl;
cout << "TC28: " << (validExpression("*(((()())())())") == true) << endl;
cout << "TC29: " << (validExpression("(((()())()))())") == false) << endl;
cout << "TC30: " << (validExpression("*(((()())())*())") == true) << endl;
}
My approach solves it in O(n).
Please mention if any issue with the approach or time complexity.
Thanks ruslanbes2 for the test cases. I have used the same for testing.
Steps:
1. Scan the string and count he number of occurrences of '(', ')' and '*'
If there is a ')' before '(' or '*' then it is not valid.
2. Check if the condition (Math.abs(rightParen - leftParen) <= starParen) satisfies.
The condition is to check if we have enough wild card *s to validate. Example *()))
3. Check if there is no *s in the String and both '(' and ')' should be equal.
4. Again scan the same string and decrement the number of occurrences calculated in the step 1.
Before decrementing check if '*' is 0 and '(' is greater than ')' then the string is not valid.
After decrementing check if ')' and '*' are 0 and '(' is greater than 0 then the string is not valid.
public class CheckParanthesis {
private static boolean checkParenthesis(String str) {
int leftParen = 0;
int rightParen = 0;
int starParen = 0;
boolean isValid = true;
// Group and Count character in the string
for (char c : str.toCharArray()) {
if (c == '(')
leftParen++;
else if (c == ')')
rightParen++;
else if (c == '*')
starParen++;
/**
* Return false when String starts with ) when there is no ( or *
**/
if (leftParen == 0 && starParen == 0 && rightParen > 0) {
return false;
}
}
/**
* When there is shortage in * and either ( or ) more then return false
**/
if (!(Math.abs(rightParen - leftParen) <= starParen))
return false;
/** if * is null and ( & ) is not equal then return false **/
if ((starParen == 0 && rightParen != leftParen)) {
return false;
}
// Scan the String and decrement the values
for (char c : str.toCharArray()) {
/** When * is empty but ( is greater than ) return false **/
if (starParen == 0 && (leftParen > rightParen)) {
return false;
}
if (c == '(')
leftParen--;
else if (c == ')')
rightParen--;
else if (c == '*')
starParen--;
/** When the string has no ) but still have ( then return false **/
if ((rightParen == 0 && starParen == 0 && leftParen > 0)) {
return false;
}
}
return isValid;
}
/**
* Test Cases
*/
@Test
public void checkParenthesis() {
assertTrue(CheckParanthesis.checkParenthesis(""));
assertTrue(CheckParanthesis.checkParenthesis("()"));
assertTrue(CheckParanthesis.checkParenthesis("(*)"));
assertTrue(CheckParanthesis.checkParenthesis("(*)(*)"));
assertTrue(CheckParanthesis.checkParenthesis("*"));
assertTrue(CheckParanthesis.checkParenthesis("**"));
assertTrue(CheckParanthesis.checkParenthesis("*)"));
assertTrue(CheckParanthesis.checkParenthesis("*(((()())()))())"));
assertFalse(CheckParanthesis.checkParenthesis("*()("));
assertFalse(CheckParanthesis.checkParenthesis("**()("));
assertFalse(CheckParanthesis.checkParenthesis("**(**)*("));
assertFalse(CheckParanthesis.checkParenthesis(")**"));
assertTrue(CheckParanthesis.checkParenthesis("****()))))"));
assertTrue(CheckParanthesis.checkParenthesis("****())))"));
assertFalse(CheckParanthesis.checkParenthesis("****())))))"));
assertFalse(CheckParanthesis.checkParenthesis("***********************(((((()"));
assertFalse(CheckParanthesis.checkParenthesis("(((()())()))())"));
assertTrue(CheckParanthesis.checkParenthesis("*(((()())())*())"));
}
@Test
public void checkParenthesis5() {
assertTrue(CheckParanthesis.checkParenthesis("(*)(*)(**"));
}
@Test
public void checkParenthesis10() {
assertTrue(CheckParanthesis.checkParenthesis("*(((()())())())"));
}
}
After posting the soln above, seems that we can have O(n2) approach, using additional space which is much cleaner -
public static void main(String[] args){
String str = "*)(*";
System.out.println(isValid(str));
}
public static boolean isValid(String str){
char[] carr = str.toCharArray();
int n = carr.length;
Stack<Character> stack = new Stack<Character>();
Queue<Character> queue = new LinkedList<Character>();
int i = 0;
while(i < n){
if(carr[i] == '(' || carr[i] == '*')
stack.push(carr[i]);
else{
while(!stack.isEmpty()){
char c = stack.pop();
if(c == '(')
continue;
else
queue.add(c);
}
}
if(!queue.isEmpty() && stack.isEmpty()){
while(!queue.isEmpty()){
stack.add(queue.poll());
}
}
i++;
}
boolean valid = true;
int countWild = 0;
if(!stack.isEmpty()){
char c = stack.pop();
if(c == '*'){
valid = true;
countWild++;
}else if(c == ')'){
valid = false;
}else if(c == '(' && countWild > 0){
countWild--;
}else if(c == '(' && countWild <= 0){
return false;
}
}
return valid;
}
My idea is first to remove all paired brackets. After that, we get something like ")))((". Then, to count how many stars and how many closing brackets are there to the left of each closing bracket. And the same logic backward pass for opening brackets.
bool Valid(string s)
{
stack<int> st;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '(') {
st.push(i);
} else if (s[i] == ')') {
if (!st.empty()) {
s[i] = ' ';
s[st.top()] = ' ';
st.pop();
}
}
}
int stars = 0;
int closings = 0;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '*') {
++stars;
} else if (s[i] == ')') {
++closings;
}
if (closings > stars) {
return false;
}
}
stars = 0;
int openings = 0;
for (int i = s.size() - 1; i >= 0; --i) {
if (s[i] == '*') {
++stars;
} else if (s[i] == '(') {
++openings;
}
if (openings > stars) {
return false;
}
}
return true;
}
static boolean isValid(String input) {
if (input == null || input.length() == 0) return false;
int count = 0;
int starCount = 0;
char arr[] = input.toCharArray();
for(char c : arr) {
switch(c) {
case ')':
count--;
break;
case '(':
count++;
break;
case '*':
starCount++;
break;
}
}
if (starCount == 0 && count == 0) return true;
if (count > 0) return (count - starCount) == 0;
if (count == 0) return Math.abs(count - starCount) % 2 == 0;
return false;
}
/**
* Givens: 1- * can work as either opening or closing parenthis, or none.
* Required: Check for string validation,, this is usually a stack problem. In
* this case, it is a stack problem, and at every wild card we need to have
* three different options. For each option (,) or *, we need to make a branch.
* Backtracking problem.
*
* Base case: location == string.length,, return test Stack General case:
*
* @param args
*/
public static Stack<Character> stack = new Stack<>();
public static void main(String[] args) {
System.out.println(isValid("(((**)",0));
}
public static boolean isValid(String s, int location) {
if (location >= s.length() - 1) {
if (s.charAt(location) == '*')
return pushToStackAndTestThenPop(null) || pushToStackAndTestThenPop(')')
|| pushToStackAndTestThenPop('(');
else
return pushToStackAndTestThenPop(s.charAt(location));
} else {
if (s.charAt(location) == '*') {
// null condition, nothing to push
if (isValid(s, location+1)) return true;
else {
stack.push('(');
if (isValid(s, location+1))
return true;
else {
stack.pop();//backtracking
stack.push(')');
return isValid(s,location+1);
}
}
} else {
stack.push(s.charAt(location));
if (isValid(s, location+1)) return true;
else {
stack.pop();//backtracking
return false;
}
}
}
}
public static boolean pushToStackAndTestThenPop(Character c) {
if (c == null)
return testStack();
else {
stack.push(c);
boolean result = testStack();
stack.pop();
return result;
}
}
//traditional string stack problem
public static boolean testStack() {
String string="";
for(int i=stack.size()-1; i>=0; i--) {
string=stack.get(i)+string;
}
Stack<Character> test=new Stack<>();
for(int i=0; i<string.length(); i++) {
if(string.charAt(i)=='(') test.push('(');
else if(string.charAt(i)==')') {
if(test.isEmpty()||test.pop()!='(') return false;
}
}
return test.isEmpty();
}
package swiggy;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class FindBalance {
public static void main(String args[]) {
System.out.println(isValid("(*)(*)(**"));
}
static boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
Stack<Character> queue = new Stack<>();
int count=0;;
int countStar=0;
int i=0;
for (i = 0; i < s.length(); i++) {
if(s.charAt(i)=='(' || s.charAt(i) == '*') {
stack.push(s.charAt(i));
}
else {
boolean isFound=false;
while(!stack.isEmpty()) {
char c = stack.pop();
if(c=='(') {
isFound = true;
break;
}else {
queue.push(c);
}
}
while(!queue.isEmpty()) {
stack.push(queue.pop());
}
if(!isFound) {
stack.push(')');
}
}
}
int star = 0;
if(!stack.isEmpty()) {
while(!stack.isEmpty() && stack.peek()!=')') {
char c = stack.pop();
if(c=='(') {
if(star>0)
star--;
else
return false;
}
if(c=='*') {
star++;
}
}
star = 0;
while(!stack.isEmpty()) {
char c = stack.pop();
if(c==')') {
star++;
}
if(c=='*') {
star--;
}
}
if(star>0) {
return false;
}
}
while(!stack.isEmpty()) {
if(stack.pop()==')'||stack.pop()=='(') {
return false;
}
}
if(stack.isEmpty()) {
return true;
}
return false;
}
}
package swiggy;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class FindBalance {
public static void main(String args[]) {
System.out.println(isValid("(*)(*)(**"));
}
static boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
Stack<Character> queue = new Stack<>();
int count=0;;
int countStar=0;
int i=0;
for (i = 0; i < s.length(); i++) {
if(s.charAt(i)=='(' || s.charAt(i) == '*') {
stack.push(s.charAt(i));
}
else {
boolean isFound=false;
while(!stack.isEmpty()) {
char c = stack.pop();
if(c=='(') {
isFound = true;
break;
}else {
queue.push(c);
}
}
while(!queue.isEmpty()) {
stack.push(queue.pop());
}
if(!isFound) {
stack.push(')');
}
}
}
int star = 0;
if(!stack.isEmpty()) {
while(!stack.isEmpty() && stack.peek()!=')') {
char c = stack.pop();
if(c=='(') {
if(star>0)
star--;
else
return false;
}
if(c=='*') {
star++;
}
}
star = 0;
while(!stack.isEmpty()) {
char c = stack.pop();
if(c==')') {
star++;
}
if(c=='*') {
star--;
}
}
if(star>0) {
return false;
}
}
while(!stack.isEmpty()) {
if(stack.pop()==')'||stack.pop()=='(') {
return false;
}
}
if(stack.isEmpty()) {
return true;
}
return false;
}
}
package swiggy;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class FindBalance {
public static void main(String args[]) {
System.out.println(isValid("(*)(*)(**"));
}
static boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
Stack<Character> queue = new Stack<>();
int count=0;;
int countStar=0;
int i=0;
for (i = 0; i < s.length(); i++) {
if(s.charAt(i)=='(' || s.charAt(i) == '*') {
stack.push(s.charAt(i));
}
else {
boolean isFound=false;
while(!stack.isEmpty()) {
char c = stack.pop();
if(c=='(') {
isFound = true;
break;
}else {
queue.push(c);
}
}
while(!queue.isEmpty()) {
stack.push(queue.pop());
}
if(!isFound) {
stack.push(')');
}
}
}
int star = 0;
if(!stack.isEmpty()) {
while(!stack.isEmpty() && stack.peek()!=')') {
char c = stack.pop();
if(c=='(') {
if(star>0)
star--;
else
return false;
}
if(c=='*') {
star++;
}
}
star = 0;
while(!stack.isEmpty()) {
char c = stack.pop();
if(c==')') {
star++;
}
if(c=='*') {
star--;
}
}
if(star>0) {
return false;
}
}
while(!stack.isEmpty()) {
if(stack.pop()==')'||stack.pop()=='(') {
return false;
}
}
if(stack.isEmpty()) {
return true;
}
return false;
}
}
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class FindBalance {
public static void main(String args[]) {
System.out.println(isValid("(*)(*)(**"));
}
static boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
Stack<Character> queue = new Stack<>();
int count=0;;
int countStar=0;
int i=0;
for (i = 0; i < s.length(); i++) {
if(s.charAt(i)=='(' || s.charAt(i) == '*') {
stack.push(s.charAt(i));
}
else {
boolean isFound=false;
while(!stack.isEmpty()) {
char c = stack.pop();
if(c=='(') {
isFound = true;
break;
}else {
queue.push(c);
}
}
while(!queue.isEmpty()) {
stack.push(queue.pop());
}
if(!isFound) {
stack.push(')');
}
}
}
int star = 0;
if(!stack.isEmpty()) {
while(!stack.isEmpty() && stack.peek()!=')') {
char c = stack.pop();
if(c=='(') {
if(star>0)
star--;
else
return false;
}
if(c=='*') {
star++;
}
}
star = 0;
while(!stack.isEmpty()) {
char c = stack.pop();
if(c==')') {
star++;
}
if(c=='*') {
star--;
}
}
if(star>0) {
return false;
}
}
while(!stack.isEmpty()) {
if(stack.pop()==')'||stack.pop()=='(') {
return false;
}
}
if(stack.isEmpty()) {
return true;
}
return false;
}
}
For an input string of length n
Time Complexity : O(n)
Space complexity : O(1)
Solution:
public static boolean validate(final String input) {
int leftParanthesesCounter = 0;
int rightParanthesesCounter = 0;
int starParanthesesCounter = 0;
for (char character : input.toCharArray()) {
if (character == '(') {
leftParanthesesCounter++;
} else if (character == ')') {
rightParanthesesCounter++;
} else if (character == '*') {
starParanthesesCounter++;
}
if (rightParanthesesCounter > leftParanthesesCounter + starParanthesesCounter) {
return false;
} else if (rightParanthesesCounter > leftParanthesesCounter) {
int delta = Math.min(starParanthesesCounter, rightParanthesesCounter - leftParanthesesCounter);
starParanthesesCounter -= delta;
leftParanthesesCounter += delta;
}
}
if (leftParanthesesCounter != rightParanthesesCounter) {
return false;
}
return true;
}
To solve this problem we can check if the string is balanced without take into account the stars. During the check we'll store the open parenthesis position in a stack and when we find a close parenthesis we extract the matching one (the open parenthesis) from the stack and replece both position on the string with empty string. This way if the string is already balanced the fina string will has only stars or nothing. If the string isn't balanced we will get a pattern where the close parenthesis are at left of the open parenthesis, something like this:
*))**))))***((((****((((****
Note: this pattern can have how many stars and parenthesis how we wish, but the condition previously mentioned will apply always (all close parenthesis are on the left of open parenthesis).
Now, we can iterate this string from left to right and assume the stars are open parenthesis until we get a real open parenthesis. We can have a counter to increment it when a star is recognize and decrement it when we find a close parenthesis. If we found a open parenthesis we reset the counter and start again but from the end of the string until the position of the first open parenthesis, again we increment the counter on stars and decrement on open parenthesis. If in any case during the iterations the counter gets a value < 0 we can say the string is balanced. This is the code:
public static Boolean isBalanced(String str){
ArrayDeque<Integer> parenthesis = new ArrayDeque<>(str.length());
ArrayDeque<Integer> bracket = new ArrayDeque<>(str.length());
ArrayDeque<Integer> keys = new ArrayDeque<>(str.length());
char[] seq = str.toCharArray();
for(int i = 0; i < str.length(); i++){
if(str.charAt(i) == '(')
parenthesis.push(i);
else if(str.charAt(i) == ')'){
if(!parenthesis.isEmpty()){
int j = parenthesis.pop();
seq[i] = ' ';
seq[j] = ' ';
}
}
else if(str.charAt(i) == '[')
bracket.push(i);
else if(str.charAt(i) == ']'){
if(!bracket.isEmpty()){
int j = bracket.pop();
seq[i] = ' ';
seq[j] = ' ';
}
}
else if(str.charAt(i) == '{')
keys.push(i);
else if(str.charAt(i) == '}'){
if(!keys.isEmpty()){
int j = keys.pop();
seq[i] = ' ';
seq[j] = ' ';
}
}
}
int count = 0;
int i = 0;
for(; i < seq.length; i++){
if(seq[i] == '*') count++;
else if(seq[i] == ')' || seq[i] == ']' || seq[i] == '}'){
count --;
if(count < 0) return false;
}
else if(seq[i] == '(' || seq[i] == '[' || seq[i] == '{'){
count = 0;
break;
}
}
for(int j = seq.length - 1; j >= i; j--){
if(seq[j] == '*') count++;
else if(seq[j] == '(' || seq[i] == '[' || seq[i] == '{'){
count--;
if(count < 0) return false;
}
}
return true;
}
The basic idea of the algorithm :
1. Start from the end of the string
2. Check for the edge cases, i.e., the string starts with ')' or ends with '('
3. Maintain two stacks -- one for the closing braces - ')' and one for the star '*'
4. If the character in the string is ')' push it in the closeBrace stack
5. If the character in the string is '*' push it in the star stack
6. If the character in the string is '(', the following cases need to be considered :
--- If both the star and closeBrace stacks are empty, return false
--- If the closeBrace stack is not empty, pop an item from closeBrace
--- If the star stack is not empty, pop an item from star
7. At the end, we keep popping from star and closeBrace stacks until any one of them is empty
8. If closeBrace stack is not empty, this means the parantheses are not balanced, we return false
9. For other cases, we return true
Time complexity : O(n), space complexity : O(n)
public static boolean isBalanced(String s) {
int start = s.length() - 1;
if(start < 0)
return true;
if(s.charAt(0) == ')' || s.charAt(s.length() - 1) == '(')
return false;
Stack<Character> closeBrace = new Stack<>();
Stack<Character> star = new Stack<>();
while(start >= 0) {
char ch = s.charAt(start);
if(ch == '(') {
if(star.isEmpty() && closeBrace.isEmpty())
return false;
if(!closeBrace.isEmpty())
{
closeBrace.pop();
}
else if(!star.isEmpty())
{
star.pop();
}
}
else if(ch == ')')
{
closeBrace.push(ch);
}
else if(ch == '*')
{
star.push('*');
}
start--;
}
while(!star.isEmpty() && !closeBrace.isEmpty()) {
star.pop();
closeBrace.pop();
}
if(!closeBrace.isEmpty())
return false;
return true;
}
package com.anton.parenthesis;
import java.rmi.UnexpectedException;
import java.util.Stack;
/**
* Created by anton.ve on 11/8/2017.
*/
public class Parenthesis {
public static boolean check(String input) throws UnexpectedException
{
int inputLen = input.length();
if (inputLen == 0)
return true;
int starsCount = 0;
int starsAfterOpeningCount = 0;
int parenthesisCount = 0;
for (int inputIndex = 0; inputIndex < inputLen; inputIndex++)
{
Character inputChar = input.charAt(inputIndex);
if (inputChar == '(')
{
parenthesisCount++;
starsAfterOpeningCount = 0;
}
else
if (inputChar == ')')
{
if (parenthesisCount == 0)
{
if (starsCount == 0)
return false;
else
starsCount--;
}
else
parenthesisCount--;
}
else
if (inputChar == '*')
{
starsCount++;
starsAfterOpeningCount++;
}
else
throw(new UnexpectedException("Unexpected input"));
}
return (starsAfterOpeningCount - parenthesisCount) >= 0;
}
}
package com.anton.parenthesis;
import org.junit.Assert;
import org.junit.Test;
import java.rmi.UnexpectedException;
/**
* Created by anton.ve on 11/8/2017.
*/
public class ParenthesisTest {
@Test
public void Test_Empty_Success() throws UnexpectedException
{
Assert.assertTrue(Parenthesis.check(""));
}
@Test
public void Test_NoStars_Success() throws UnexpectedException
{
Assert.assertTrue(Parenthesis.check("((()))()"));
}
@Test
public void Test_NoStars_Fail() throws UnexpectedException
{
Assert.assertFalse(Parenthesis.check("(()))()"));
}
@Test
public void Test_NoStarsOpening_Fail() throws UnexpectedException
{
Assert.assertFalse(Parenthesis.check("(((("));
}
@Test
public void Test_Stars_Succeeded() throws UnexpectedException
{
Assert.assertTrue(Parenthesis.check("((***))**(****)"));
}
@Test
public void Test_ParenthesisMissing_Succeeded() throws UnexpectedException
{
Assert.assertTrue(Parenthesis.check("((***)))**(****)"));
}
@Test
public void Test_StarsOpening_Fail() throws UnexpectedException
{
Assert.assertFalse(Parenthesis.check("*("));
}
@Test
public void Test_StarsNotEnough_Fail() throws UnexpectedException
{
Assert.assertFalse(Parenthesis.check("**())))"));
}
@Test
public void Test_CareerCup() throws UnexpectedException
{
Assert.assertTrue(Parenthesis.check(""));
Assert.assertTrue(Parenthesis.check("()"));
Assert.assertTrue(Parenthesis.check("(*)"));
Assert.assertTrue(Parenthesis.check("(*)(*)"));
Assert.assertTrue(Parenthesis.check("*"));
Assert.assertTrue(Parenthesis.check("**"));
Assert.assertTrue(Parenthesis.check("*)"));
Assert.assertTrue(Parenthesis.check("*(((()())()))())"));
Assert.assertFalse(Parenthesis.check("*()("));
Assert.assertFalse(Parenthesis.check("**()("));
Assert.assertFalse(Parenthesis.check("**(**)*("));
Assert.assertFalse(Parenthesis.check(")**"));
Assert.assertTrue(Parenthesis.check("****()))))"));
Assert.assertTrue(Parenthesis.check("****())))"));
Assert.assertFalse(Parenthesis.check("****())))))"));
Assert.assertFalse(Parenthesis.check("***********************(((((()"));
Assert.assertTrue(Parenthesis.check("(*)(*)(**"));
Assert.assertTrue(Parenthesis.check("*(((()())())())"));
Assert.assertFalse(Parenthesis.check("(((()())()))())"));
Assert.assertTrue(Parenthesis.check("*(((()())())*())"));
Assert.assertTrue(Parenthesis.check("(*)"));
Assert.assertTrue(Parenthesis.check("((*)"));
Assert.assertTrue(Parenthesis.check("((*))"));
Assert.assertTrue(Parenthesis.check("((*)))"));
Assert.assertFalse(Parenthesis.check("((*))))"));
Assert.assertTrue(Parenthesis.check("*((*))))"));
Assert.assertTrue(Parenthesis.check("(*((*))))"));
Assert.assertTrue(Parenthesis.check("(*)(*)(**"));
Assert.assertTrue(Parenthesis.check("(*)(*)(***"));
Assert.assertTrue(Parenthesis.check("((*)(*)(***"));
Assert.assertFalse(Parenthesis.check("(()(*)("));
Assert.assertFalse(Parenthesis.check("(()(*)("));
Assert.assertTrue(Parenthesis.check("****()))))"));
Assert.assertTrue(Parenthesis.check(""));
Assert.assertTrue(Parenthesis.check("()"));
Assert.assertTrue(Parenthesis.check("(*)"));
Assert.assertTrue(Parenthesis.check("(*)(*)"));
Assert.assertTrue(Parenthesis.check("*"));
Assert.assertTrue(Parenthesis.check("**"));
Assert.assertTrue(Parenthesis.check("*)"));
Assert.assertTrue(Parenthesis.check("*(((()())()))())"));
Assert.assertFalse(Parenthesis.check("*()("));
Assert.assertFalse(Parenthesis.check("**()("));
Assert.assertFalse(Parenthesis.check("**(**)*("));
Assert.assertFalse(Parenthesis.check(")**"));
Assert.assertTrue(Parenthesis.check("****()))))"));
Assert.assertTrue(Parenthesis.check("****())))"));
Assert.assertFalse(Parenthesis.check("****())))))"));
Assert.assertFalse(Parenthesis.check("***********************(((((()"));
Assert.assertTrue(Parenthesis.check("*(((()())())())"));
Assert.assertFalse(Parenthesis.check("(((()())()))())"));
Assert.assertTrue(Parenthesis.check("*(((()())())*())"));
}
}
public static boolean isBalanced(String string) {
char[] chars = string.toCharArray();
int length = chars.length;
int[] pitfalls = new int[length];
int[] parenthesis = new int[length];
int numParenthesis = 0;
int numPitfalls = 0;
if (length == 0) {
return true;
}
if (chars[0] == ')' || chars[length-1] == '(') {
return false;
}
for (int index = 0; index < length; index++) {
char currChar = chars[index];
if (currChar == '(') {
parenthesis[numParenthesis++] = index;
pitfalls[index] = numPitfalls;
} else if (currChar == ')') {
if (numParenthesis > 0) {
parenthesis[numParenthesis--] = -1;
} else if (numPitfalls == 0) {
return false;
} else {
numPitfalls--;
}
pitfalls[index] = numPitfalls;
} else if (currChar == '*') {
pitfalls[index] = ++numPitfalls;
}
}
for (int parents = numParenthesis -1; parents >= 0; parents--) {
int index = parenthesis[parents];
if ( (numPitfalls - pitfalls[index]) == 0) {
return false;
}
numPitfalls--;
}
return true;
}
public static boolean isBalanced(String string) {
char[] chars = string.toCharArray();
int length = chars.length;
int[] pitfalls = new int[length];
int[] parenthesis = new int[length];
int numParenthesis = 0;
int numPitfalls = 0;
if (length == 0) {
return true;
}
if (chars[0] == ')' || chars[length-1] == '(') {
return false;
}
for (int index = 0; index < length; index++) {
char currChar = chars[index];
if (currChar == '(') {
parenthesis[numParenthesis++] = index;
pitfalls[index] = numPitfalls;
} else if (currChar == ')') {
if (numParenthesis > 0) {
parenthesis[numParenthesis--] = -1;
} else if (numPitfalls == 0) {
return false;
} else {
numPitfalls--;
}
pitfalls[index] = numPitfalls;
} else if (currChar == '*') {
pitfalls[index] = ++numPitfalls;
}
}
for (int parents = numParenthesis -1; parents >= 0; parents--) {
int index = parenthesis[parents];
if ( (numPitfalls - pitfalls[index]) == 0) {
return false;
}
numPitfalls--;
}
return true;
}
import java.util.Scanner;
import java.util.Stack;
public class ParanthesisBalance {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String str = scanner.nextLine();
scanner.close();
System.out.println(checkIfValidParantheses(str.toCharArray()));
}
private static boolean checkIfValidParantheses(char[] str) {
Stack<Integer> openParanthesesStack = new Stack<>();
Stack<Integer> closeParanthesesStack = new Stack<>();
Stack<Integer> asterixParanthesesStack = new Stack<>();
for (int i = 0; i < str.length; i++) {
if (str[i] == '(') {
openParanthesesStack.push(i);
} else if (str[i] == ')') {
if (!openParanthesesStack.isEmpty()) {
str[openParanthesesStack.pop()] = '.';
} else {
closeParanthesesStack.push(i);
}
} else {
asterixParanthesesStack.push(i);
}
}
if (openParanthesesStack.isEmpty() && closeParanthesesStack.isEmpty()) {
return true;
} else if (!openParanthesesStack.isEmpty()) {
if (asterixParanthesesStack.size() < openParanthesesStack.size()) {
return false;
}
while (!openParanthesesStack.isEmpty()) {
if (openParanthesesStack.pop() > asterixParanthesesStack.pop()) {
return false;
}
}
return true;
} else {
if (asterixParanthesesStack.size() < closeParanthesesStack.size()) {
return false;
}
while (!closeParanthesesStack.isEmpty()) {
if (closeParanthesesStack.pop() < asterixParanthesesStack.pop()) {
return false;
}
}
return true;
}
}
}
public boolean isBalanced(String s) {
Stack<Integer> obIdxStack = new Stack<>(), starIdxStack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch == '*') {
starIdxStack.push(i);
} else if (ch == '(') {
obIdxStack.push(i);
} else {
if (obIdxStack.size() > 0) {
obIdxStack.pop();
} else {
if (starIdxStack.isEmpty()) {
return false;
}
starIdxStack.pop();
}
}
}
while (!obIdxStack.isEmpty()) {
int top1 = obIdxStack.pop();
if (starIdxStack.isEmpty() || starIdxStack.peek() < top1) {
return false;
}
starIdxStack.pop();
}
return true;
}
Checking if an expression is balanced can be done in O(n) by using a stack and it's a very well known problem. For this problem we can extend the idea and use backtracking to handle the wildcards. Time complexity would be O(3^n).
import java.util.*;
import java.lang.*;
import java.io.*;
public class Main {
public static boolean isBalanced(String exp){
int n = exp.length();
char[] expArray = new char[n];
for (int i = 0; i < n; i++){
expArray[i] = exp.charAt(i);
}
return helper(expArray, 0, new Stack<Character>());
}
public static boolean helper(char[] exp, int index, Stack<Character> stack){
int n = exp.length;
if (index == n){
return stack.isEmpty();
}
else {
char c = exp[index];
if (c == '('){
stack.push(c);
boolean result = helper(exp, index + 1, stack);
stack.pop();
return result;
}
else if (c == ')'){
if (stack.isEmpty()){
return false;
}
stack.pop();
boolean result = helper(exp, index + 1, stack);
stack.push(c);
return result;
}
else{
// c == '*'
}
if (helper(exp, index + 1, stack)){
return true;
}
exp[index] = '(';
if (helper(exp, index, stack)){
return true;
}
exp[index] = ')';
return helper(exp, index, stack);
}
}
public static void main (String[] args){
System.out.println(isBalanced("(*)(*)(**"));
}
}
boolean checkParenthesis(String str) {
int lp = 0;
int rp = 0;
int sp = 0;
boolean isValid = true;
for(char c : str.toCharArray()){
if(c == '(') lp++;
else if(c == ')') rp++;
else if(c == '*') sp++;
}
for(char c : str.toCharArray()){
if(c == '(') lp--;
else if(c == ')') rp--;
else if(c == '*') sp--;
}
if((lp==0 && sp==0 && rp>0) || (rp==0 && sp== 0 && lp>0) || (lp==0 && rp== 0 && sp>0)){
isValid = false;
}
return isValid;
}
Brute Force -
public static void main(String[] args) {
String str = "(*)(*)(**";
char[] carr = str.toCharArray();
System.out.println(validString(carr, 0, false));
}
// (*)(*)(**
public static boolean validString(char[] carr, int i, boolean valid) {
int n = carr.length;
Stack<Character> stack = new Stack<Character>();
while (i < n) {
if (carr[i] == '(' || carr[i] == ' ')
stack.push(carr[i]);
else if (carr[i] == ')') {
while (!stack.isEmpty()) {
char c = stack.pop();
if (c == ' ')
continue;
else if (c == ')')
return false;
else
break;
}
} else if (carr[i] == '*') {
carr[i] = '(';
valid |= validString(carr, 0, valid);
carr[i] = ')';
valid |= validString(carr, 0, valid);
carr[i] = ' ';
valid |= validString(carr, 0, valid);
carr[i] = '*';
}
i++;
}
while (!stack.isEmpty() && stack.peek() == ' ')
stack.pop();
if (stack.isEmpty())
valid = true;
else if(!valid)
valid = false;
return valid;
}
The most important thing is to know what are the exact rules of using the wildcard character.
Assumptions:
1. wildcard max count sequentially is 2.
2. wildcard can open, close or be inside parenthesis.
3. if a wildcard is used to close parenthesis then it should be used twice, like in the example.
package com.cracking.amazon;
import java.util.EmptyStackException;
import java.util.Stack;
public class ValidateParenthesisStr {
public static enum Parenthesis {
REGULAR( '(', ')' ),
SQUARE( '[', ']' ),
CURLED( '{', '}' ),
WILDCARD( '*', '*');
Parenthesis(char openChar, char closeChar) {
this.openChar = openChar;
this.closeChar = closeChar;
}
public char openChar;
public char closeChar;
public boolean isParenthesis(char ch) {
return this.openChar == ch || this.closeChar == ch;
}
}
public static final String input = "(*)(*)(*){**";
public static void main(String[] args) {
String output = String.format("Input = %s\nValidation = %s\n", input,validate(input));
System.out.println(output);
}
public static boolean validate(String input) {
Stack<Parenthesis> parenthesisStack = new Stack<Parenthesis>();
for(int i=0; i<input.length(); i++) {
char ch = input.charAt(i);
Parenthesis ps = getParenthesis(ch);
if(ps == null) return false;
if(ps == Parenthesis.WILDCARD && !parenthesisStack.isEmpty() && parenthesisStack.peek() == Parenthesis.WILDCARD) {
// 2 wildcards sequentially
parenthesisStack.pop(); //pop wildcard
if(!parenthesisStack.isEmpty()) parenthesisStack.pop(); //pop open char if exist
continue;
}
if(ch == ps.openChar) {
parenthesisStack.push(ps);
continue;
}
try {
Parenthesis openP = parenthesisStack.pop();
if(openP == ps) {
//No action needed
}else if(openP == Parenthesis.WILDCARD && parenthesisStack.isEmpty()) {
//No action needed
}else if(openP == Parenthesis.WILDCARD && parenthesisStack.peek() == ps) {
openP = parenthesisStack.pop();
}else {
return false;
}
}catch(EmptyStackException e) {
return false;
}
}
return parenthesisStack.isEmpty();
}
public static Parenthesis getParenthesis(char ch) {
if( Parenthesis.REGULAR.isParenthesis(ch) ) {
return Parenthesis.REGULAR;
}
if( Parenthesis.SQUARE.isParenthesis(ch) ) {
return Parenthesis.SQUARE;
}
if( Parenthesis.CURLED.isParenthesis(ch) ) {
return Parenthesis.CURLED;
}
if( Parenthesis.WILDCARD.isParenthesis(ch) ) {
return Parenthesis.WILDCARD;
}
return null;
}
}
#include <stack>
#include <iostream>
#include <string>
void main()
{
string teststrings[] = { "*)",
"()",
"(*)(*)",
"",
"(*)",
"*",
"**",
"*(((()())()))())",
"*()(",
"**()(",
"**(**)*(",
")**",
"****()))))",
"****())))",
"****())))))",
"***********************(((((()" };
string valid[] = { "Not Valid", "Valid" };
for each (string var in teststrings)
{
bool Res = ValidateParenthesis_withwideChar(var);
cout << var << "\t" << valid[Res] << "\n";
}
}
static bool ValidateParenthesis_withwideChar(string str)
{
bool valid = true;
stack<char> *Left_Parenthesis = new stack<char>();
stack<char> *stars = new stack<char>();
char *y = &str[0];
while (*y) {
if (*y == '(')
{
Left_Parenthesis->push(*y);
}
else if(*y == '*')
{
stars->push(*y);
}
else if (*y == ')')
{
// Both stacks are Empty
if (Left_Parenthesis->empty() && stars->empty())
{
return false;
}
// Left is not
else if(!Left_Parenthesis->empty())
{
Left_Parenthesis->pop();
}
// Left is Empty and Stars is not
else if(Left_Parenthesis->empty() && !stars->empty())
{
stars->pop();
}
}
y++;
}
return Left_Parenthesis->empty();
}
boolean checkParenthesis(String str) {
int lp = 0;
int rp = 0;
int sp = 0;
boolean isValid = true;
for(char c : str.toCharArray()){
if(c == '(') lp++;
else if(c == ')') rp++;
else if(c == '*') sp++;
}
for(char c : str.toCharArray()){
if(c == '(') lp--;
else if(c == ')') rp--;
else if(c == '*') sp--;
}
if((lp==0 && sp==0 && rp>0) || (rp==0 && sp== 0 && lp>0) || (lp==0 && rp== 0 && sp>0)){
isValid = false;
}
return isValid;
}
First of all, my Test Set. Use it to check your solution (hint: many of the solutions here fail it)
My approach solves it in O(n^2). And handles all of the cases regardless of the number and position of characters in a string. It's pretty brute-force but it does the job. This is a solution for the simple case. For the case with "[]" and "{}" you just have to call it 3 times passing bracket chars as parameters
- ruslanbes2 October 17, 2017