Reference: Link

241. Different Ways to Add Parentheses (Medium)

We can use divide and conquer to solve this problem. We divide the string at the position of operators. For example, compute 1+1. We treat 1+1 as ()+(). We need to find all possible values for the left and right brackets. And compute the sum of all these possible values. Therefore, we need to use recursion to find all possible values. We keep dividing until we find there is no operator in the input string. This means the input string is only a number. We just return it as the only possible value.

We can also use a hashmap to reduce running time. We define a global hashmap. The key is string, value is a list of all possible values generated by computing the key. In each recursion, we find if this string is the key of hashmap. If hashmap contains this string, we just return the value, because we already computed all possible values. This way can help us to avoid computing same string again and again.

Here is the link.

public List<Integer> diffWaysToCompute(String input) {
    List<Integer>res = new ArrayList();
    for(int i =0;i<input.length();i++){
        Character operator = input.charAt(i);
        if(operator == '+'||operator == '*'||operator == '-'){
            List<Integer>left = diffWaysToCompute(input.substring(0,i));
            List<Integer>right = diffWaysToCompute(input.substring(i+1));
            for(int m =0;m<left.size();m++){
                for(int j =0;j<right.size();j++){
                    if(operator == '+'){
                        res.add(left.get(m)+right.get(j));
                    }
                    else if(operator == '-'){
                        res.add(left.get(m)-right.get(j));
                    }
                    else
                        res.add(left.get(m)*right.get(j));
                }
            }
        }
    }
    if(res.size()==0)
        res.add(Integer.valueOf(input));
    return res;

}

95. Unique Binary Search Trees II (Medium)

The solution of this problem is similar to the last problem. We divide n this time. For example, we start from i (1<=i<=n). We take i as the head. And compute the left subtree and right subtree. Left subtree is consist of (1,i-1). Right subtree is consist of (i+1,n). And in recursion, we do this again and again until we find all possible subtrees. And combine all possible subtrees to get our answer.

We can also use a 2D array as our memory to avoid computing same subtree again. (i,j) means the range of the subtree. This can help us reduce running time.

Here is the link.

public List<TreeNode> generateTrees(int n) {
    if(n==0)return new ArrayList();
    return help(1,n);
}
public List<TreeNode> help(int low, int high){
    List<TreeNode>ans = new ArrayList();
    if(low>high){
        ans.add(null);
        return ans;
    }
    for(int i =low;i<=high;i++){   
        List<TreeNode>left = help(low,i-1);
        List<TreeNode>right = help(i+1,high);
        for(int m =0;m<left.size();m++){
            for(int n = 0;n<right.size();n++){
                TreeNode head = new TreeNode(i);
                head.left = left.get(m);
                head.right = right.get(n);
                ans.add(head);
            }
        }
    }
    return ans;
}