# 0241. Different Ways to Add Parentheses
###### tags: `Leetcode` `Medium` `FaceBook`
Link: https://leetcode.com/problems/different-ways-to-add-parentheses/
## 思路
用recursive
这题用map记录substring和对应产生的结果list，可以显著提升速度~
时间复杂度比较复杂，不太确定是多少，只知道一共有多种group方法 [reference](https://people.math.sc.edu/howard/Classes/554b/catalan.pdf)，对于每个group的方法，都需要不断切割substring

## Code

class Solution {
    Map<String, List<Integer>> map = new HashMap<>();
    public List<Integer> diffWaysToCompute(String expression) {
        List<Integer> ans = new ArrayList<>();
        boolean isNum = true;
        int num = 0;
        for(int i = 0;i < expression.length();i++){
            if(!Character.isDigit(expression.charAt(i))){
                isNum = false;
                String leftStr = expression.substring(0,i);
                String rightStr = expression.substring(i+1, expression.length());
                List<Integer> leftAns, rightAns;
                if(!map.containsKey(leftStr)) leftAns = diffWaysToCompute(expression.substring(0,i));
                leftAns = map.get(leftStr);
                if(!map.containsKey(rightStr)) rightAns = diffWaysToCompute(expression.substring(i+1,expression.length()));
                rightAns = map.get(rightStr);
                for(int leftNum:leftAns){
                    for(int rightNum:rightAns){
                        if(expression.charAt(i)=='+'){
                            ans.add(leftNum+rightNum);
                        }
                        else if(expression.charAt(i)=='-'){
                            ans.add(leftNum-rightNum);
                        }
                        else if(expression.charAt(i)=='*'){
                            ans.add(leftNum*rightNum);
                        }
                    }
                }
            }
        }
        if(ans.size()==0){
            ans.add(Integer.valueOf(expression));
        }
        map.put(expression, ans);
        return ans;
    }
}