Leetcode 241 Different Ways to Add Parentheses

思路：我一开始的想法是将括号插入到input中，罗列出所有可能的情况。然后判断expression是否valid，怎么判断在Leetcode 20 Valid Parentheses讲解过。最后再把所有valid expression计算出结果就vans了。可惜第一步就没实现，因为根本不能确定要在input哪个地方插入括号，你总不能在一个+号的前后加上括号吧。我也不太清楚我这种思路能不能实现，也许可以，但是工作量一定会非常大，面试的时候也就20分钟，这种算法就离谱，果断放弃。好了那我没思路了，康康答案吧。好嘛，没答案。。。行吧那就去看discussion吧，害，果然高手在民间啊。看到了一个recursive的做法，一开始我还看不懂人家写的代码，还放进ide里debug了。我也是服了，后来看懂了，发现人家写的是真的好啊，一行废话都没有，牛皮就vans了。话说这种recursive的算法是真的不太容易想到，首先你要找到这个recursive的规律，然后还要有非常强的逻辑，空间结构，因为是一环套一环的。I hope i can code like this in the very soon!下面给出代码：

public class Solution {
public List<Integer> diffWaysToCompute(String input) {
    
        //basic condition when input doesn't contain any operators.    
    	if((input.contains("+") || input.contains("-") || input.contains("*")) != true) {
    		int i =Integer.valueOf(input);
    		List<Integer> res = new ArrayList<Integer>();
    		res.add(i);
    		return res;
    	}
    	
        List<Integer> ret = new LinkedList<Integer>();
        for (int i=0; i<input.length(); 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> part1Ret = diffWaysToCompute(part1); // do the recursion
                List<Integer> part2Ret = diffWaysToCompute(part2);
                for (Integer p1 :   part1Ret) {
                    for (Integer p2 :   part2Ret) {
                        int c = 0;
                        switch (input.charAt(i)) {
                            case '+': c = p1+p2;
                                break;
                            case '-': c = p1-p2;
                                break;
                            case '*': c = p1*p2;
                                break;
                        }
                        ret.add(c);
                    }
                }
            }
        }
        return ret;
    }
}

但是这个写法还是有一点缺陷的，会出现大量的重复计算。我是看到底下评论才发觉到的，确实，这边可以用一个hashmap来存储（input，输出的list），下次再次需要运算diffWaysToCompute（input）时，直接进map里调用就好了，就不需要重新计算了。

总结：

1. 大家讨论一下recursive的算法的利弊，我是觉得会大量减轻代码量，很讨巧的方法，但是搞的不好可能会导致运行时间过长，内存占用过大，程序效率低的问题。不知道大家怎么认为。但无论如何，recursive绝对是一种聪明人的做法。