package leetcode;

/**
 * https://leetcode.com/problems/valid-parenthesis-string/
 */
public class Problem678 {
    public boolean checkValidString(String s) {
        return check(s, 0, 0);
    }

    private static boolean check(String s, int idx, int opening) {
        if (opening < 0) {
            return false;
        }
        if (s.length() == idx) {
            if (opening == 0) {
                return true;
            }
            return false;
        }
        if (s.charAt(idx) == '(') {
            return check(s, idx + 1, opening + 1);
        } else if (s.charAt(idx) == ')') {
            return check(s, idx + 1, opening - 1);
        } else {
            boolean a = check(s, idx + 1, opening + 1); // (
            boolean b = check(s, idx + 1, opening); // )
            boolean c = check(s, idx + 1, opening - 1); // empty
            return a || b || c;
        }
    }

    public static void main(String[] args) {
        Problem678 prob = new Problem678();
        System.out.println(prob.checkValidString("()")); // true
        System.out.println(prob.checkValidString("(*)")); // true
        System.out.println(prob.checkValidString("(*))")); // true
        System.out.println(prob.checkValidString(")(")); // false
        System.out.println(prob.checkValidString("()()")); // true
        System.out.println(prob.checkValidString("(**())")); // true
    }
}

@@ -165,180 +165,78 @@
     
-return check(s, 0,
+int opening =
  0
-)
 ;%0A    
-%7D%0A%0A
     
-private static boolean check(String s, int idx, int opening) %7B%0A        if (opening %3C 0) %7B%0A            return false;%0A        %7D%0A        if (
+int closing = 0;%0A        for (int i = 0; i %3C 
 s.le
@@ -245,15 +245,13 @@
 th()
- == idx
+; i++
 ) %7B%0A
@@ -270,20 +270,26 @@
 if (
-opening
+s.charAt(i)
  == 
-0
+'('
 ) %7B%0A
@@ -308,19 +308,17 @@
     
-return true
+opening++
 ;%0A  
@@ -332,34 +332,15 @@
    %7D
-%0A            return false;
+ else %7B
 %0A   
@@ -348,18 +348,16 @@
     
-%7D%0A
         
 if (
@@ -356,101 +356,44 @@
     
-if (s.charAt(idx) == '(') %7B%0A            return check(s, idx + 1, opening + 1);%0A        %7D else
+opening--;%0A            %7D%0A           
  if 
@@ -403,18 +403,16 @@
 charAt(i
-dx
 ) == ')'
@@ -431,247 +431,120 @@
     
-return check(s, idx + 1, opening - 1);%0A        %7D else %7B%0A            boolean a = check(s, idx + 1, opening + 1); // (%0A            boolean b = check(s, idx + 1, opening); // )%0A            boolean c = check(s, idx + 1, opening - 1); // empty%0A
+    closing--;%0A            %7D else %7B%0A                closing++;%0A            %7D%0A            if (closing %3C 0) %7B%0A    
     
@@ -562,19 +562,13 @@
 urn 
-a %7C%7C b %7C%7C c
+false
 ;%0A  
@@ -577,505 +577,96 @@
     
-%7D%0A
     %7D%0A
-%0A
     
-public static void main(String%5B%5D args) %7B%0A        Problem678 prob = new Problem678();%0A        System.out.println(prob.checkValidString(%22()%22)); // true%0A        System.out.println(prob.checkValidString(%22(*)%22)); // true%0A        System.out.println(prob.checkValidString(%22(*))%22)); // true%0A        System.out.println(prob.checkValidString(%22)(%22)); // false%0A        System.out.println(prob.checkValidString(%22()()%22)); // true%0A        System.out.println(prob.checkValidString(%22(**())%22)); // true
+        opening = Math.max(opening, 0);%0A        %7D%0A        return opening == 0;
 %0A   

Solve problem 678