iLoveCoding85
BAN USERMy 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("*(((()())())())"));
}
}
RepMaryGriffith, Cloud Support Associate at Auto NInja
I am Mary , have graduated with marketing specialization and I am passionate about Internet Marketing and Social Media. Creates business ...
RepAadhikLee, abc at 8x8
Expedite data entry efforts and bank reconciliation under the direct guidance of the senior accountant, ensuring clean, accurate financial records ...
RepZoeParker, Java Experienced at Abs india pvt. ltd.
I am Zoe , a Security Analyst with a record of success in completing financial market research and conducting earnings estimates ...
Replindagwingard, Android test engineer at ABC TECH SUPPORT
Hello, my name is Larry and I am a commercial loan officer. We are commercial loan officers who specialize in ...
RepNirvedPerez, abc at 8x8
To make sure a thorough investigation is done if discrepancies occur. Execute the Brand Customer Service standards to meet or ...
RepIsabellaJones, abc at 8x8
Extensive experience of 3 years in network architecture and application requirements for corporate data and voice networks, planning, designing and ...
Repjj2234971, Applications Developer at ABC TECH SUPPORT
My role for teaching students in a particular subject area. I specialize in a variety of subjects and fields. such ...
RepJohnPitts, Development Support Engineer at Barclays Capital
John , an urban regional planner with over four years of experience helping cities and local areas to properly plan for ...
Reppfisterruiz, Accountant at 247quickbookshelp
Door-to-door is a canvassing technique that is generally used for sales, marketing, advertising, evangelism or campaigning, in which I walk ...
RepShivelyFauver, Animator at AMD
Project Management Assistant with a proven record in developing and managing project budgets, completing presentations and reports. As nowadays astrology ...
Repbrianlwarren596, Android Engineer at 247quickbookshelp
Hey my name is BrainWarren and I am working as an Interpreter.my main work is Interpreters and translators convert ...
Repdelioshorn, Member Technical Staff at Atmel
Attentive Teller Supervisor with 4 years of experience in assisting customers to meet financial needs and referring customers to partners ...
RepHeldaNate, Dev Lead at AMD
I am Helda , a certified Swimming Instructor capable of providing professional lessons and instructions on different swimming styles to various ...
Finds longest path of a tree. The longest path may not be through the root.
Used custom object TResult.
Time complexity : O(n)
Kindly suggest for any improvement in the code.
- iLoveCoding85 October 21, 2017