package com.fishercoder.solutions;

import java.util.LinkedList;
import java.util.List;

/**
 * 241. Different Ways to Add Parentheses
 *
 * Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.


 Example 1
 Input: "2-1-1".

 ((2-1)-1) = 0
 (2-(1-1)) = 2
 Output: [0, 2]


 Example 2
 Input: "2*3-4*5"

 (2*(3-(4*5))) = -34
 ((2*3)-(4*5)) = -14
 ((2*(3-4))*5) = -10
 (2*((3-4)*5)) = -10
 (((2*3)-4)*5) = 10
 Output: [-34, -14, -10, -10, 10]

 */
public class _241 {
    /**Time:  O(n * 4^n / n^(3/2)) ~= n * Catalan numbers = n * (C(2n, n) - C(2n, n - 1)),
                                     due to the size of the results is Catalan numbers,
                                     and every way of evaluation is the length of the string,
                                     so the time complexity is at most n * Catalan numbers.
      Space: O(n * 4^n / n^(3/2)), the cache size of lookup is at most n * Catalan numbers.*/

    /**Credit: https://discuss.leetcode.com/topic/19901/a-recursive-java-solution-284-ms*/
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> answer = new LinkedList<>();
        int len = input.length();
        for (int i = 0; i < len; i++) {
            if (input.charAt(i) == '+'
                    || input.charAt(i) == '-'
                    || input.charAt(i) == '*') {
                String part1 = input.substring(0, i);
                String part2 = input.substring(i + 1);
                List<Integer> answer1 = diffWaysToCompute(part1);
                List<Integer> answer2 = diffWaysToCompute(part2);
                for (int a1 : answer1) {
                    for (int a2 : answer2) {
                        int result = 0;
                        switch (input.charAt(i)) {
                            case '+':
                                result = a1 + a2;
                                break;
                            case '-':
                                result = a1 - a2;
                                break;
                            case '*':
                                result = a1 * a2;
                                break;
                            default:
                                break;
                        }
                        answer.add(result);
                    }
                }
            }
        }
        if (answer.size() == 0) {
            answer.add(Integer.valueOf(input));
        }
        return answer;
    }

}

@@ -590,16 +590,56 @@
  _241 %7B%0A
+    public static class Solution1 %7B%0A    
     /**T
@@ -725,36 +725,8 @@
 )),%0A
-                            
     
@@ -785,36 +785,8 @@
 rs,%0A
-                            
     
@@ -851,36 +851,8 @@
 ng,%0A
-                            
     
@@ -911,16 +911,19 @@
 umbers.%0A
+   
       Sp
@@ -1013,19 +1013,35 @@
 */%0A%0A    
-/**
+    /**%0A         * 
 Credit: 
@@ -1113,19 +1113,33 @@
 n-284-ms
+%0A         
 */%0A
+    
     publ
@@ -1189,32 +1189,36 @@
 nput) %7B%0A        
+    
 List%3CInteger%3E an
@@ -1248,24 +1248,28 @@
 ();%0A        
+  
+  
 int len = in
@@ -1278,24 +1278,28 @@
 t.length();%0A
+    
         for 
@@ -1322,24 +1322,28 @@
 len; i++) %7B%0A
+    
             
@@ -1381,32 +1381,36 @@
                 
+    
 %7C%7C input.charAt(
@@ -1419,16 +1419,20 @@
  == '-'%0A
+    
         
@@ -1480,32 +1480,36 @@
                 
+  
+  
 String part1 = i
@@ -1530,16 +1530,20 @@
 (0, i);%0A
+    
         
@@ -1597,32 +1597,36 @@
                 
+   
+ 
 List%3CInteger%3E an
@@ -1655,24 +1655,28 @@
 ute(part1);%0A
+    
             
@@ -1737,32 +1737,36 @@
                 
+    
 for (int a1 : an
@@ -1786,32 +1786,36 @@
                 
+ 
+   
 for (int a2 : an
@@ -1843,24 +1843,28 @@
             
+    
 int result =
@@ -1891,16 +1891,20 @@
         
+  
+  
 switch (
@@ -1946,24 +1946,28 @@
             
+    
 case '+':%0A  
@@ -1964,16 +1964,20 @@
 se '+':%0A
+    
         
@@ -2042,39 +2042,47 @@
                 
+    
 break;%0A
+    
                 
@@ -2127,32 +2127,36 @@
                 
+ 
+   
 result = a1 - a2
@@ -2181,32 +2181,36 @@
                 
+    
 break;%0A         
@@ -2224,24 +2224,28 @@
             
+   
+ 
 case '*':%0A  
@@ -2242,16 +2242,20 @@
 se '*':%0A
+    
         
@@ -2292,24 +2292,28 @@
  = a1 * a2;%0A
+    
             
@@ -2367,16 +2367,20 @@
         
+    
 default:
@@ -2404,32 +2404,36 @@
                 
+    
 break;%0A         
@@ -2439,34 +2439,42 @@
                 
+  
-%7D%0A
+  %7D%0A    
                 
@@ -2513,34 +2513,42 @@
                 
+   
+ 
 %7D%0A
+    
                 
@@ -2553,32 +2553,36 @@
   %7D%0A            
+    
 %7D%0A        %7D%0A    
@@ -2567,34 +2567,42 @@
       %7D%0A        
+ 
-%7D%0A
+   %7D%0A    
         if (answ
@@ -2623,32 +2623,36 @@
 ) %7B%0A            
+  
+  
 answer.add(Integ
@@ -2671,34 +2671,42 @@
 nput));%0A        
-%7D%0A
+    %7D%0A    
         return a
@@ -2716,13 +2716,22 @@
 er;%0A    
+    %7D%0A    
 %7D
-%0A
 %0A%7D%0A

refactor 241