LeetCode 241 - Different Ways to Add Parentheses


[LeetCode]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]
X. 分治法（Divide and conquer），递归地将表达式按照运算符拆分为左右两半

时间复杂度为所有可能的结果数，具体为卡特兰数 。
  1. 分治法 + 递归法：时间复杂度O(2^n)，空间复杂度O(n*2^n)。
    • 遍历字符串，遇到符号时，将字符串左右分别当作相同的问题处理，递归得到左右结果，
    • 可以用unordered_map<string,vector<int>>，以substring为键值的哈希表来记录已经计算过的值，来降低复杂度：
      • 时间复杂度O(Cat(n))，空间复杂度O(n*Cat(n))
    • 复杂度的计算：
      • 时间复杂度是卡塔兰数O(Cat(n))：Cat(n) = C(2n, n)/(n + 1)，因为可能组合数：a(n)=a(0)*a(n)+a(1)*a(n-1)+...+a(n)*a(0)
      • 因此空间复杂度，是时间复杂度的基础上，每次递归复制参数再乘以n：O(n*Cat(n))
  2. 动态规划（DP）：时间复杂度O(Cat(n))，空间复杂度O(n^2*Cat(n))。
    • 此题想要用DP来解，就最好不使用string来构建DP表，string之间的比较比较复杂
    • 将所有的数和操作符从string中取出，然后再建立dp[i][j]储存从第i个数到第j个数所有可能的结果：
      • 初始化：dp[i][i] = {nums[i]}
      • 更新dp，(j:0->n，i:j->0)：dp[i][j] = dp[i][k] *+- dp[k + 1][j] (i < k < j)
      • 返回：dp[0][n - 1]
http://buttercola.blogspot.com/2015/09/leetcode-different-ways-to-add.html


The problem itself is not hard. The essence of the problem is to compute the different ways to compute the expression. There is only one trick here is how to handle the input has only one number there, e.g. "1". Then we need to add the number into the result list. The idea is to check if the result is empty after the divide-and-conquer step. If it is empty, means only one number left in the input. Note that we cannot check using if the first character of the input string is digit, because each and every input string starts from a number. 
https://discuss.leetcode.com/topic/31622/my-recursive-java-solution/4
For the first round, you have n-1 choices to combine any 2 numbers. In the second round, you have n-2 choices, .... So, it is: (n-1)(n-2)(n-3)....*1
https://discuss.leetcode.com/topic/19911/what-is-the-time-complexity-of-divide-and-conquer-method
With n being the number of operators, it's at least Ω(3^n).
f(n) = f(1)+f(2)+..+f(n-1)+f(n-1)+f(n-2)..+f(1) = 2*(f(1)+f(2)+...+f(n-1))
=> 
f(n+1) = 2*(f(1)+f(2)+..+f(n)) = 2*(f(1)+f(2)+...+f(n-1)) + 2f(n) = f(n)+2f(n) = 3f(n) 
=> 
f(n+1) = 3f(n) = 3*3*f(n-1) = ... = 3^(n+1)

Therefore, O(3^n)
https://stackoverflow.com/questions/27371612/catalan-numbers-recursive-function-time-complexity/27374250#27374250
To evaluate the complexity, let us focus on the number of recursive calls performed, let C(n).

A call for n implies exactly 2(n-1) recursive calls, each of them adding their own costs, 2(C(1)+C(2)+...C(n-1)).

A call for n+1 implies exactly 2n recursive calls, each of them adding their own costs, 2(C(1)+C(2)+...C(n-1)+C(n)).

By difference, C(n+1)-C(n) = 2+2C(n), which can be written C(n) = 2+3C(n-1).

C(1) = 0
C(2) = 2+2C(1) = 2+3C(0) = 2
C(3) = 4+2(C(1)+C(2)) = 2+3C(2) = 8
C(3) = 6+2(C(1)+C(2)+C(3)) = 2+3C(3) = 26
C(4) = 8+2(C(1)+C(2)+C(3)+C(4)) = 2+3C(4) = 80
...
C(n) = 2n-2+2(C(1)+C(2)+...C(n-1)) = 2+3C(n-1)
To solve this recurrence easily, notice that

C(n)+1 = 3(C(n-1)+1) = 9(C(n-2)+1) = ...3^(n-2)(C(2)+1) = 3^(n-1)
Hence, for n>1 the exact formula is

C(n) = 3^(n-1)-1
The number of calls to Catalan(1) (constant time), is also C(n), and the numbers of adds or multiplies are C(n)/2 each.

It is easy to reduce the complexity from O(3^n) to O(2^n) by noting that all terms in the loop (except the middle one) are computed twice - but that still doesn't make it an acceptable implementation :)

http://www.cnblogs.com/yrbbest/p/5006196.html
这道题的主要意思就是我们可以任意加括号来破坏运算符的计算规则，返回所有可能的值。这里很像Unique Binary Search Tree II, 我们需要先递归计算运算符左半边的结果，和运算符右半边的结果，然后使用双重循环，根据运算符来把最终结果加入到结果集res中去。要注意的是递归到最后，我们的base case是没有运算符，只有数字的时候， 这时我们可以直接把这个数加入到结果集里。时间复杂度应该是catalan number，空间复杂度也是指数级。
Time Complexity - O(2n)， Space Complexity - O(2n)
http://likesky3.iteye.com/blog/2231382
思路类似Unique Binary Search Trees II，以某个运算符为分界线，递归计算左右两边可能的值，然后根据当前运算符归并结果。纯粹的递归含有冗余计算，可同时保留中间结果来提高效率。 
http://justcodings.blogspot.com/2015/09/leetcode-different-ways-to-add.html
Now, the problems that ask for "all possible results" is usually solved using DFS approach. Don't get confused about the * operator as it would be treated equivalently as the + and - because of the parentheses. In the end, all the question asks is to find all possible combinations using parentheses.
http://codechen.blogspot.com/2015/07/leetcode-different-ways-to-add.html
https://leetcode.com/discuss/48477/a-recursive-java-solution-284-ms

  • 直接使用递归, 通过operator作为分割点, 对左右expr进行recursion得到的list来for loop得到当前expression的解并放入到结果list.
  • 需要注意边界条件.
This is a nice and clean solution. However, note that there are many overlapping sub-problems, dynamic programming should be a potential way to improve the performance.
Using a map to memorize would be better.


    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> result = new ArrayList<Integer>();
        if (input == null || input.length() == 0) {
            return result;
        }
        
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (c != '+' && c != '-' && c != '*') {
                continue;
            }
            
            List<Integer> part1Result = 
                diffWaysToCompute(input.substring(0, i));
            List<Integer> part2Result = 
                diffWaysToCompute(input.substring(i + 1, input.length()));
            
            for (Integer m : part1Result) {
                for (Integer n : part2Result) {
                    if (c == '+') {
                        result.add(m + n);
                    } else if (c == '-') {
                        result.add(m - n);
                    } else if (c == '*') {
                        result.add(m * n);
                    }
                }
            }
        }
        
        if (result.size() == 0) {
            result.add(Integer.parseInt(input));
        }
        
        return result;
    }
https://discuss.leetcode.com/topic/19901/a-recursive-java-solution-284-ms/12
    Map<String, List<Integer>> map = new HashMap<>();
    
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (c == '+' || c == '-' || c == '*') {
                String p1 = input.substring(0, i);
                String p2 = input.substring(i + 1);
                List<Integer> l1 = map.getOrDefault(p1, diffWaysToCompute(p1));
                List<Integer> l2 = map.getOrDefault(p2, diffWaysToCompute(p2));
                for (Integer i1 : l1) {
                    for (Integer i2 : l2) {
                        int r = 0;
                        switch (c) {
                            case '+':
                                r = i1 + i2;
                                break;
                            case '-':
                                r = i1 - i2;
                                break;
                            case '*':
                                r = i1 * i2;
                                break;
                        }
                        res.add(r);
                    }
                }
            }
        }
        if (res.size() == 0) {
            res.add(Integer.valueOf(input));
        }
        map.put(input, res);
        return res;
    }
https://leetcode.com/discuss/74276/my-recursive-java-solution
-- better to use expression to detect there is no operator.
List<Integer> list=new ArrayList(); if(input==null||input.length()==0) return list; if(!input.contains("+")&&!input.contains("-")&&!input.contains("*")) {//\\ list.add(Integer.valueOf(input));//\\ return list;//\\ } for(int i=0;i<input.length();i++){ char ops=input.charAt(i); if(ops=='+'||ops=='-'||ops=='*'){ List<Integer> leftList=diffWaysToCompute(input.substring(0,i)); List<Integer> rightList=diffWaysToCompute(input.substring(i+1,input.length())); for(int leftValue:leftList){ for(int rightValue:rightList){ switch(ops){ case '+': list.add(leftValue+rightValue); break; case '-': list.add(leftValue-rightValue); break; case '*': list.add(leftValue*rightValue); break; } } } } } return list; }
https://leetcode.com/discuss/61840/java-recursive-9ms-and-dp-4ms-solution
I think it's more efficient to pre-parse the string because String.substring() is costly. I store the parsed string in a list, for example, if the string is 1+2+3+4, then the list will contain:
"1", "+", "2", "+", "3", "+", "4"
Personally I feel this is also more convenient because all integers occurs at even indices (0, 2, 4, 6) and all operators are at odd indices (1, 3, 5).
Then the problem is very similar to "Unique Binary Search Trees II". For each operator in the list, we compute all possible results for entries to the left of that operator, which is List<Integer> left, and also all possible results for entries to the right of that operator, namely List<Integer> right, and combine the results. It can be achieved by recursion or more efficiently by dp.
public List<Integer> diffWaysToCompute(String input) { List<Integer> result=new ArrayList<>(); if(input==null||input.length()==0) return result; List<String> ops=new ArrayList<>(); for(int i=0; i<input.length(); i++){ int j=i; while(j<input.length()&&Character.isDigit(input.charAt(j))) j++; String num=input.substring(i, j); ops.add(num); if(j!=input.length()) ops.add(input.substring(j, j+1)); i=j; } result=compute(ops, 0, ops.size()-1); return result; } private List<Integer> compute(List<String> ops, int lo, int hi){ List<Integer> result=new ArrayList<>(); if(lo==hi){ Integer num=Integer.valueOf(ops.get(lo)); result.add(num); return result; } for(int i=lo+1; i<=hi-1; i=i+2){ String operator=ops.get(i); List<Integer> left=compute(ops,lo, i-1), right=compute(ops, i+1, hi); for(int leftNum:left) for(int rightNum: right){ if(operator.equals("+")) result.add(leftNum+rightNum); else if(operator.equals("-")) result.add(leftNum-rightNum); else result.add(leftNum*rightNum); } } return result; }
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < input.length(); i++) {
            if (isOperator(input.charAt(i))) {
                char operator = input.charAt(i);
                List<Integer> left = diffWaysToCompute(input.substring(0, i));
                List<Integer> right = diffWaysToCompute(input.substring(i + 1));
                for (int num1 : left) {
                    for (int num2 : right) {
                        result.add(calculate(num1, num2, operator));
                    }
                }
            }
        }
        if (result.size() == 0) {
            result.add(Integer.valueOf(input));
        }
        return result;
    }
Utility(跟面试官说一下就行):
public int calculate(int num1, int num2, char operator) {
    int result = 0;
    switch(operator) {
        case '+' : result = num1 + num2;
        break;
         
        case '-' : result = num1 - num2;
        break;
         
        case '*' : result = num1 * num2;
        break;
    }
    return result;
}
public boolean isOperator(char c) {
    if (c == '+' || c == '-' || c == '*')
        return true;
    return false;
}
X. 使用memorization的recursion
https://leetcode.com/discuss/48490/java-recursive-solution-with-memorization
public List<Integer> diffWaysToCompute(String input) { //cache for memorization HashMap<String,List<Integer>> cache = new HashMap<String,List<Integer>>(); return this.helper(input,cache); } List<Integer>helper(String s, HashMap<String,List<Integer>> cache) { if (cache.get(s)!=null) { return cache.get(s); } boolean expression = false; // this is clearer ArrayList<Integer> result = new ArrayList<Integer>(); for(int i=0; i<s.length(); i++) { if("+-*".indexOf(s.charAt(i))!=-1) { List<Integer> left = helper(s.substring(0,i),cache); List<Integer> right = helper(s.substring(i+1),cache); for(Integer l: left) { for(Integer r: right) { result.add(cal(l,r,s.charAt(i))); } } expression = true; } } if (!expression) { // base case, there is only number no operator. result.add(Integer.parseInt(s)); } cache.put(s, result); return result; } int cal(int l, int r, char op) { int result = 0; switch (op) { case '+': result= l+r; break; case '-': result = l-r; break; case '*': result= l*r; break; default: break; } return result; }


https://fxrcode.gitbooks.io/leetcodenotebook/content/Leetcode_Medium/different_ways_to_add_parentheses.html
  • 很明显: 每一个表达式很有可能在左右都遇到, 如果左边的同一个表达式已经计算过了, 那么右边出现的同样表示就直接返回结果了. 即memorization的recursion写法. 可以加速一点.
-- too many substring
public List<Integer> diffWaysToCompute(String input) {
    Map<String, List<Integer>> cache = new HashMap<>();
    return helper(input, cache);
  }

private List<Integer> helper(String s, Map<String, List<Integer>> cache) {
    if (cache.get(s) != null) {
      return cache.get(s);  // 这里就发现为什么map定义成List而不是Integer了: 因为可以直接return了.
    }
    boolean expr = false;
    List<Integer> result = new ArrayList<>();
    for (int i = 0; i < s.length(); ++i) {
      if ("+-*".indexOf(s.charAt(i)) != -1) {
        for (int left : helper(s.substring(0, i), cache)) {
        for (int right : helper(s.substring(i + 1), cache)) {
            result.add(s.charAt(i) == '+' ? left + right
                : s.charAt(i) == '-' ? left - right : left * right);
        }
        }
        expr = true;
      }
    }
    if (!expr) result.add(Integer.parseInt(s));
    cache.put(s, result);
    return result;
}
http://likesky3.iteye.com/blog/2231382
  1.     public List<Integer> diffWaysToCompute(String input) {  
  2.         HashMap<String, List<Integer>> dpMap = new HashMap<String, List<Integer>>();  
  3.         return computeWithDP(input, dpMap);  
  4.     }  
  5.     public List<Integer> computeWithDP(String input, HashMap<String, List<Integer>> dpMap) {  
  6.         List<Integer> result = new ArrayList<Integer>();  
  7.         if (input == null || input.length() == 0) return result;  
  8.         int N = input.length();  
  9.         for (int i = 0; i < N; i++) {  
  10.             char c = input.charAt(i);  
  11.             if (c == '+' || c == '-' || c == '*') {  
  12.                 String leftSubStr = input.substring(0, i);  
  13.                 String rightSubStr = input.substring(i + 1, N);  
  14.                 List<Integer> left = dpMap.get(leftSubStr);  
  15.                 if (left == null)  
  16.                     left = computeWithDP(leftSubStr, dpMap);  
  17.                 List<Integer> right = dpMap.get(rightSubStr);  
  18.                 if (right == null)  
  19.                     right = computeWithDP(rightSubStr, dpMap);  
  20.                 for (int op1: left) {  
  21.                     for (int op2: right) {  
  22.                         if (c == '+')  
  23.                             result.add(op1 + op2);  
  24.                         else if (c == '-')  
  25.                             result.add(op1 - op2);  
  26.                         else  
  27.                             result.add(op1 * op2);  
  28.                     }  
  29.                 }  
  30.             }  
  31.         }  
  32.         //if the string contains only number  
  33.         if (result.isEmpty())  
  34.             result.add(Integer.parseInt(input));  
  35.         dpMap.put(input, result);  
  36.         return result;  
  37.     }  

http://taoalpha.me/blog/2016/01/31/oj-oj-parentheses-problems/
https://leetcode.com/discuss/48488/c-4ms-recursive-%26-dp-solution-with-brief-explanation
https://leetcode.com/discuss/64418/5ms-java-recursive-with-cache-hashmap
public List<Integer> diffWaysToCompute(String input) {
    Map<String, List<Integer>> cache = new HashMap<>();
    return diffWaysToCompute(input, cache);
}

private List<Integer> diffWaysToCompute(String input, Map<String, List<Integer>> cache) {
    if(cache.containsKey(input)) return cache.get(input);

    List<Integer> vals = new ArrayList<Integer>();
    for(int i=0; i<input.length(); i++) {
        if(!operators.contains(input.charAt(i))) continue;

        char operator = input.charAt(i);
        List<Integer> leftVals = diffWaysToCompute(input.substring(0,i), cache);
        List<Integer> rightVals = diffWaysToCompute(input.substring(i+1), cache);

        for(Integer left : leftVals) {
            for(Integer right : rightVals) {
                if(operator == '+') {
                    vals.add(left + right);
                } else if(operator == '-') {
                    vals.add(left - right);
                } else if(operator == '*') {
                    vals.add(left*right);
                }
            }
        }
    }

    // number only
    if(vals.size() == 0) {
        vals.add(Integer.parseInt(input));
    }

    cache.put(input, vals);
    return vals;
}
X. DP
I think it's more efficient to pre-parse the string because String.substring() is costly. I store the parsed string in a list, for example, if the string is 1+2+3+4, then the list will contain:
"1", "+", "2", "+", "3", "+", "4"
Personally I feel this is also more convenient because all integers occurs at even indices (0, 2, 4, 6) and all operators are at odd indices (1, 3, 5).
Then the problem is very similar to "Unique Binary Search Trees II". For each operator in the list, we compute all possible results for entries to the left of that operator, which is List<Integer> left, and also all possible results for entries to the right of that operator, namely List<Integer> right, and combine the results. It can be achieved by recursion or more efficiently by dp.
And DP, where dp[i][j] stores all possible results from the i-th integer to the j-th integer (inclusive) in the list.
public List<Integer> diffWaysToCompute(String input) {
    List<Integer> result=new ArrayList<>();
    if(input==null||input.length()==0)  return result;
    List<String> ops=new ArrayList<>();
    for(int i=0; i<input.length(); i++){
        int j=i;
        while(j<input.length()&&Character.isDigit(input.charAt(j)))
            j++;
        ops.add(input.substring(i, j));
        if(j!=input.length())   ops.add(input.substring(j, j+1));
        i=j;
    }
    int N=(ops.size()+1)/2; //num of integers
    ArrayList<Integer>[][] dp=(ArrayList<Integer>[][]) new ArrayList[N][N];
    for(int d=0; d<N; d++){
        if(d==0){
            for(int i=0; i<N; i++){
                dp[i][i]=new ArrayList<>();
                dp[i][i].add(Integer.valueOf(ops.get(i*2)));//\\
            }
            continue;
        }
        for(int i=0; i<N-d; i++){
            dp[i][i+d]=new ArrayList<>();
            for(int j=i; j<i+d; j++){
                ArrayList<Integer> left=dp[i][j], right=dp[j+1][i+d];
                String operator=ops.get(j*2+1);
                for(int leftNum:left)
                    for(int rightNum:right){
                        if(operator.equals("+"))
                            dp[i][i+d].add(leftNum+rightNum);
                        else if(operator.equals("-"))
                            dp[i][i+d].add(leftNum-rightNum);
                        else
                            dp[i][i+d].add(leftNum*rightNum);
                    }
            }
        }
    }
    return dp[0][N-1];
}

  • 既然上面已经写出了recursion with memorization了. 那么DP怎么写呢?
  • 定义state: 即dp[i][j], 表示[i...j]之间所能得到的所有可能值.
  • 这种分段型的dp都是外层loop循环段的长度, 然后i,j分别表示起点,终点. 这里的细节要熟练.
public List<Integer> diffWaysToComputeBest(String input) {
    List<Integer> result = new ArrayList<>();
    if (input == null || input.length() == 0) return result;
    List<String> ops = new ArrayList<>();
    // 先是将所有数字和'+-*'放到list里
    for (int i = 0; i < input.length(); ++i) {
      int j = i;
      while (j < input.length() && Character.isDigit(input.charAt(j))) {
        j++;
      }
      ops.add(input.substring(i, j));
      if (j != input.length()) ops.add(input.substring(j, j + 1));
      i = j;
    }
    int N = (ops.size() + 1) >> 1;//??
    List<Integer>[][] dp = (ArrayList<Integer>[][])new ArrayList[N][N];
    // 按照state的长度打表
    for (int len = 0; len < N; ++len) {
      if (len == 0) {
        for (int i = 0; i < N; ++i) {
          dp[i][i] = new ArrayList<>();
          dp[i][i].add(Integer.valueOf(ops.get(i * 2)));
        }
        continue; // 计算完len = 0的之后就update len, 所以要continue
      }
      for (int i = 0; i < N - len; ++i) {
        dp[i][i + len] = new ArrayList<>();
        for (int j = i; j < i + len; ++j) {
          // 由于是按照state的长度来loop, 所以此时已经计算完所有len = 0到len-1的了!
          List<Integer> left = dp[i][j], right = dp[j + 1][i + len];  
          for (int l : left) {
            for (int r : right) {
              String op = ops.get(j * 2 + 1);
              dp[i][i + len].add(op.equals("+") ? l + r : op.equals("-") ? l - r : l * r);
            }
          }
        }
      }
    }
    return dp[0][N - 1];
}

And DP, where dp[i][j] stores all possible results from the i-th integer to the j-th integer (inclusive) in the list.
public List<Integer> diffWaysToCompute(String input) { List<Integer> result=new ArrayList<>(); if(input==null||input.length()==0) return result; List<String> ops=new ArrayList<>(); for(int i=0; i<input.length(); i++){ int j=i; while(j<input.length()&&Character.isDigit(input.charAt(j))) j++; ops.add(input.substring(i, j)); if(j!=input.length()) ops.add(input.substring(j, j+1)); i=j; } int N=(ops.size()+1)/2; //num of integers ArrayList<Integer>[][] dp=(ArrayList<Integer>[][]) new ArrayList[N][N]; for(int d=0; d<N; d++){ if(d==0){ for(int i=0; i<N; i++){ dp[i][i]=new ArrayList<>(); dp[i][i].add(Integer.valueOf(ops.get(i*2))); } continue; } for(int i=0; i<N-d; i++){ dp[i][i+d]=new ArrayList<>(); for(int j=i; j<i+d; j++){ ArrayList<Integer> left=dp[i][j], right=dp[j+1][i+d]; String operator=ops.get(j*2+1); for(int leftNum:left) for(int rightNum:right){ if(operator.equals("+")) dp[i][i+d].add(leftNum+rightNum); else if(operator.equals("-")) dp[i][i+d].add(leftNum-rightNum); else dp[i][i+d].add(leftNum*rightNum); } } } } return dp[0][N-1]; }

https://leetcode.com/discuss/51448/java-dp-solution
public List<Integer> diffWaysToCompute(String input) { List<Integer> nums = new ArrayList<Integer>(); List<Character> ops = new ArrayList<Character>(); decode(input,nums,ops); List<Integer> ans = new ArrayList<Integer>(); int len = nums.size(); List<List<List<Integer>>> dp = new ArrayList<List<List<Integer>>>(); for(int i=0;i<len;i++) dp.add(new ArrayList<List<Integer>>()); for(int i=0;i<len;i++) for(int j=0;j<len;j++) dp.get(i).add(new ArrayList<Integer>()); for(int i=0;i<len;i++) dp.get(i).get(i).add(nums.get(i));//dp[i][i]=nums[i] for(int dist=1;dist<len;dist++){ //dp[begin][end] = dp[begin][k] ops[k] dp[k+1[end];(begin<=k<end) for(int begin=0;begin<len-dist;begin++){ int end = begin+dist; for(int k=begin;k<end;k++){ for(int i=0;i<dp.get(begin).get(k).size();i++) for(int j=0;j<dp.get(k+1).get(end).size();j++) dp.get(begin).get(end).add(compute(dp.get(begin).get(k).get(i),ops.get(k),dp.get(k+1).get(end).get(j))); } } } return dp.get(0).get(len-1); }

public List<Integer> diffWaysToCompute(String input) { List<Integer> nums = new ArrayList<>(); List<Character> ops = new ArrayList<>(); decode(input, nums, ops); int len = nums.size(); List<Integer>[][] dp = new ArrayList[len][len]; for (int i = 0; i < len; i++) { for (int j = 0; j < len; j++) { dp[i][j] = new ArrayList<>(); } } for (int i = 0; i < len; i++) { dp[i][i].add(nums.get(i)); // dp[i][i] = nums[i] } for (int dist = 1; dist < len; dist++) { for (int begin = 0; begin < len - dist; begin++) { int end = begin + dist; // dp[begin][end] = dp[begin][k] ops[k] dp[k+1][end] (begin <= k < end) for (int k = begin; k < end; k++) { for (int left : dp[begin][k]) { for (int right : dp[k + 1][end]) { dp[begin][end].add(compute(left, ops.get(k), right)); } } } } } return dp[0][len - 1]; } private void decode(String input, List<Integer> nums, List<Character> ops) { int i = 0, len = input.length(); while (i < len) { int num = 0; while (i < len) { char c = input.charAt(i); if (c < '0' || c > '9') { break; } num = num * 10 + c - '0'; i++; } nums.add(num); if (i < len) { ops.add(input.charAt(i)); i++; } } }
http://yuanhsh.iteye.com/blog/2230557
  1. public List<Integer> diffWaysToCompute(String s) {  
  2.     String[] arr = s.split("[\\+\\-\\*\\/]");  
  3.     String[] ops = s.split("\\d+"); // Note: the 1st item is a space  
  4.     int n = arr.length;  
  5.     int[] nums = new int[n];  
  6.     for(int i=0; i<n; i++) {  
  7.         nums[i] = Integer.parseInt(arr[i].trim());  
  8.     }  
  9.     return diffWays(nums, ops, 0, n-1);  
  10. }  
  11.   
  12. public List<Integer> diffWays(int[] nums, String[] ops, int left, int right) {  
  13.     List<Integer> list  = new ArrayList<>();  
  14.     if(left == right) {  
  15.         list.add(nums[left]);  
  16.         return list;  
  17.     }  
  18.     for(int i=left+1; i<=right; i++) {  
  19.         List<Integer> list1 = diffWays(nums, ops, left, i-1);  
  20.         List<Integer> list2 = diffWays(nums, ops, i, right);  
  21.         for(int num1:list1) {  
  22.             for(int num2:list2) {  
  23.                 switch(ops[i].charAt(0)) {  
  24.                     case '+': list.add(num1+num2); break;  
  25.                     case '-': list.add(num1-num2); break;  
  26.                     case '*': list.add(num1*num2); break;  
  27.                     case '/': list.add(num1/num2); break;  
  28.                 }  
  29.             }  
  30.         }  
  31.     }  
  32.     return list;  
  33. }  
private final static long base = 100001;
private Map<Long, List<Integer>> cache = new HashMap<>();
private List<Integer> diffWaysToCompute(char[] cs, int start, int end) {
    long key = base * start + end;
    if (cache.containsKey(key)) {
        return cache.get(key);
    }
    boolean isNumber = true;
    for (int i = start; i < end; i++) {
        if (isOperator(cs[i])) {
            isNumber = false;
            break;
        }
    }
    List<Integer> result = new ArrayList<>();
    if (isNumber) {
        result.addAll(toNum(cs, start, end));
    } else {
        for (int i = start; i < end; i++) {
            if (isOperator(cs[i])) {
                List<Integer> prev = diffWaysToCompute(cs, start, i);
                List<Integer> suff = diffWaysToCompute(cs, i + 1, end);
                result.addAll(combineResult(prev, suff, cs[i]));
            }
        }
        return result;
    }
    cache.put(key, result);
    return result;
}
private List<Integer> combineResult(List<Integer> prev, List<Integer> suff, char op) {
    List<Integer> result = new ArrayList<>();
    for (int x : prev) {
        for (int y : suff) {
            result.add(calculate(x, y, op));
        }
    }
    return result;
}
private int calculate(int x, int y, char op) {
    switch (op) {
        case '+':
            return x + y;
        case '-':
            return x - y;
        case '*':
            return x * y;
    }
    return 0;
}
private List<Integer> toNum(char[] cs, int start, int end) {
    int num = 0;
    for (int i = start; i < end; i++) {
        if (cs[i] == ' ') {
            continue;
        }
        num = num * 10 + (cs[i] - '0');
    }
    List<Integer> result = new ArrayList<>(1);
    result.add(num);
    return result;
}
private boolean isOperator(char c) {
    return c == '+' || c == '-' || c == '*';
}
public List<Integer> diffWaysToCompute(String input) {
    return diffWaysToCompute(input.toCharArray(), 0, input.length());
}

class Solution: # @param {string} input # @return {integer[]} def diffWaysToCompute(self, input): def calc(a, b, o): return {'+':lambda x,y:x+y, '-':lambda x,y:x-y, '*':lambda x,y:x*y}[o](a, b) def dfs(nums, ops): if not ops: return [nums[0]] ans = [] for x in range(len(ops)): left = dfs(nums[:x+1], ops[:x]) right = dfs(nums[x+1:], ops[x+1:]) for l in left: for r in right: ans.append(calc(l, r, ops[x])) return ans nums, ops = [], [] input = re.split(r'(\D)', input) for x in input: if x.isdigit(): nums.append(int(x)) else: ops.append(x) return dfs(nums, ops)
http://shibaili.blogspot.com/2015/08/day-119-239-sliding-window-maximum.html
X. DFS
    vector<int> diffWaysToCompute(string s) {
        vector<int> rt;
         
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '-' || s[i] == '+' || s[i] == '*') {
                vector<int> first = diffWaysToCompute(s.substr(0,i));
                vector<int> second = diffWaysToCompute(s.substr(i + 1));
                for (int j = 0; j < first.size(); j++) {
                    for (int k = 0; k < second.size(); k++) {
                        if (s[i] == '-') {
                            rt.push_back(first[j] - second[k]);
                        }
                        if (s[i] == '+') {
                            rt.push_back(first[j] + second[k]);
                        }
                        if (s[i] == '*') {
                            rt.push_back(first[j] * second[k]);
                        }
                    }
                }
            }
        }
        if (rt.size() == 0) rt.push_back(stoi(s));
        return rt;
DP优化
    vector<int> helper(string s, int start, int end,unordered_map<string,vector<int>> &dic) {
        vector<int> rt;
         
        for (int i = start; i <= end; i++) {
            if (s[i] == '-' || s[i] == '+' || s[i] == '*') {
                vector<int> first;
                vector<int> second;
                if (dic.find(s.substr(start,i)) == dic.end()) {
                    first = helper(s,start,i - 1,dic);
                }else first = dic[s.substr(start,i)];
                 
                if (dic.find(s.substr(i + 1)) == dic.end()) {
                    second = helper(s,i + 1,end,dic);
                }else second = dic[s.substr(i + 1)];
                 
                for (int j = 0; j < first.size(); j++) {
                    for (int k = 0; k < second.size(); k++) {
                        if (s[i] == '-') {
                            rt.push_back(first[j] - second[k]);
                        }
                        if (s[i] == '+') {
                            rt.push_back(first[j] + second[k]);
                        }
                        if (s[i] == '*') {
                            rt.push_back(first[j] * second[k]);
                        }
                    }
                }
            }
        }
        if (rt.size() == 0) rt.push_back(stoi(s.substr(start,end - start + 1)));
        dic[s] = rt;
        return rt;
    }
     
    vector<int> diffWaysToCompute(string input) {
        unordered_map<string,vector<int>> dic;
        return helper(input,0,input.length() - 1,dic);
    }

回溯法（Backtracking），时间复杂度O(n!)，n为运算符的个数
通过dict保存有效的加括号方案，使用内置函数expr计算结果
class Solution: # @param {string} input # @return {integer[]} def diffWaysToCompute(self, input): exprDict = dict() def dfs(nums, ops): if ops: for x in range(len(ops)): dfs(nums[:x]+['('+nums[x]+ops[x]+nums[x+1]+')']+nums[x+2:],ops[:x]+ops[x+1:]) elif nums[0] not in exprDict: exprDict[nums[0]] = eval(nums[0]) nums, ops = [], [] input = re.split(r'(\D)', input) for x in input: if x.isdigit(): nums.append(x) else: ops.append(x) dfs(nums, ops) return exprDict.values()

count how many ways there are
http://blog.welkinlan.com/2015/09/11/different-ways-to-add-parentheses-leetcode-java/
    public static int diffWaysToCompute(String input) {
        int countOp = getCountOperators(input);
        int[] dp = new int[countOp + 1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 5;
        return helper(countOp, dp);
    }
    
    private static int helper(int numOp, int[] dp) {
        if (dp[numOp] != 0) {
            return dp[numOp];
        }
        int result = 0;
        for (int i = 1; i < numOp; i++) {
            result += helper(i, dp) * helper(numOp - i, dp);
        }
        return result;
    }
    
    private static int getCountOperators(String input) {
        int r = 0;
        for (int i = 0; i < input.length(); i++) {
            if (!Character.isDigit(input.charAt(i))) {
                r++;
            }
        }
        return r;
    }
    public static void main(String[] args){
     String a = "1+2+3+4+4+5";
     System.out.print(diffWaysToCompute(a));
    }

at
Labels: , , , , , , , , , , , ,

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts