package coding4fun;

import java.util.ArrayList;
import java.util.List;

/**
 * Given a simple regular like-expression. Print all possible strings that match
 * the expression.
 *
 * <pre>
 * Input : abc(de|fh|g(h|i))
 * Output: [abcde, abcfh, abcgh, abcgi]
 *
 * Input : abc(de|fh|g(h|i(jk|lm|mn))
 * Output: [abcde, abcfh, abcgh, abcgijk, abcgilm, abcgimn]
 *
 * Input : abcdef
 * Output: [abcdef]
 *
 * Input : abc(de|fh|g(h|i))j
 * Output: [abcdej, abcfhj, abcghj, abcgij]
 * </pre>
 */
public class Problem56 {
    private static List<String> allStrings(String s) {
        return allStrings(s, new IntRef());
    }

    private static List<String> allStrings(String s, IntRef ref) {
        List<String> strings = new ArrayList<>();
        String tmp = "";
        while (ref.val < s.length()) {
            int i = ref.val;
            if (s.charAt(i) == '(') {
                ref.val++;
                strings.add(tmp);
                List<String> allStrings = allStrings(s, ref);
                for (String a : allStrings) {
                    strings.add(tmp + a);
                }
                tmp = "";
            } else if (s.charAt(i) == '|') {
                ref.val++;
                strings.add(tmp);
                tmp = "";
            } else if (s.charAt(i) == ')') {
                ref.val++;
                if (!tmp.isEmpty()) {
                    strings.add(tmp);
                }
                return strings;
            } else {
                ref.val++;
                tmp += s.charAt(i);
            }
        }
        if (strings.isEmpty()) {
            strings.add(tmp);
        } else {
            for (int i = 0; i < strings.size(); i++) {
                strings.set(i, strings.get(i) + tmp);
            }
        }
        return strings;
    }

    private static class IntRef {
        private int val;
    }

    public static void main(String[] args) {
//        System.out.println(allStrings("abc(de|fh|g(h|i(jk|lm|mn))"));
//        System.out.println(allStrings("abc(de|fh|g(h|i))"));
//        System.out.println(allStrings("abc(de|fh|g(h|i))j"));
//        System.out.println(allStrings("abcdef"));
        System.out.println(allStrings("abc(de|fh|g(h|i))j(k|l)"));
    }
}

@@ -476,142 +476,1067 @@
 %5D%0A *
- %3C/pre%3E%0A */%0Apublic class Problem56 %7B%0A    private static List%3CString%3E allStrings(String s) %7B%0A        return allStrings(s, new IntRef())
+%0A * Input : abc(de%7Cfh%7Cg(h%7Ci))j(k%7Cl)%0A * Output: %5Babcdejk, abcdejl, abcfhjk, abcfhjl, abcghjk, abcghjl, abcgijk, abcgijl%5D%0A *%0A * Input : abc(de%7Cfh%7Cg(h%7Ci))j(k%7Cl)m%0A * Output: %5Babcdejkm, abcdejlm, abcfhjkm, abcfhjlm, abcghjkm, abcghjlm, abcgijkm, abcgijlm%5D%0A * %3C/pre%3E%0A */%0Apublic class Problem56 %7B%0A    private static List%3CString%3E allStrings(String s) %7B%0A        IntRef ref = new IntRef();%0A        List%3CString%3E allStrings = new ArrayList%3C%3E();%0A        while (ref.val %3C s.length()) %7B%0A            List%3CString%3E strings = allStrings(s, ref);%0A            List%3CString%3E newString = new ArrayList%3C%3E();%0A            if (allStrings.isEmpty()) %7B%0A                allStrings = strings;%0A            %7D else %7B%0A                for (String a : allStrings) %7B%0A                    for (String b : strings) %7B%0A                        newString.add(a + b);%0A                    %7D%0A                %7D%0A                allStrings = newString;%0A            %7D%0A            if (ref.val %3C s.length() && s.charAt(ref.val) == ')') %7B%0A                ref.val++;%0A            %7D%0A        %7D%0A        return allStrings
 ;%0A  
@@ -1819,42 +1819,8 @@
 ++;%0A
-                strings.add(tmp);%0A
     
@@ -1995,32 +1995,38 @@
             
-tmp = %22%22
+return strings
 ;%0A          
@@ -2520,148 +2520,8 @@
 p);%0A
-        %7D else %7B%0A            for (int i = 0; i %3C strings.size(); i++) %7B%0A                strings.set(i, strings.get(i) + tmp);%0A            %7D%0A
     
@@ -2668,18 +2668,16 @@
 args) %7B%0A
-//
         
@@ -2734,26 +2734,24 @@
 lm%7Cmn))%22));%0A
-//
         Syst
@@ -2795,26 +2795,24 @@
 g(h%7Ci))%22));%0A
-//
         Syst
@@ -2865,10 +2865,8 @@
 ));%0A
-//
     
@@ -2974,20 +2974,88 @@
 )j(k%7Cl)%22));%0A
+        System.out.println(allStrings(%22abc(de%7Cfh%7Cg(h%7Ci))j(k%7Cl)m%22));%0A
     %7D%0A%7D%0A

Update problem 56