[LeetCode] Different ways to add parentheses

Problem statement (link):

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]

Analysis:

This problem statement is a bit misleading (in a good way) so that my first attempt is to construct the different parenthesesed strings, and compute each string individually. This approach is exponential in both space and time complexity.

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.

With that, we could construct the solutions bottom-up. It's exactly the same as Unique Binary Tree II problem if we think each node as an arithmetic string. For instance,  in Example 2, we have the following ways of constructing the solutions:

Recursion Trees:
1)
                                        2 * 3 - 4 * 5
                                      /                     \
                                   2                   3 - 4 * 5
                                                       /             \
                                                     3             4 * 5
                                                                     /     \
                                                                    4      5
2)
                                        2 * 3 - 4 * 5
                                      /                     \
                                 2 * 3                  4 * 5
                                /       \                 /        \
                              2          3            4           5
3) ...
4) ...
5) ...

You get the idea.

Only extra work we need to do is instead of connecting the nodes, we compute each node (arithmetic string). The time complexity is still exponential but the code looks very clean.

Code:

public class Solution {
    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=='*') {
                for (Integer int1: diffWaysToCompute(input.substring(0, i))) {
                    for (Integer int2: diffWaysToCompute(input.substring(i+1))) { // i+1: to skip the operator char
                        res.add(c=='+' ? int1+int2 : c=='-' ? int1-int2 : int1*int2);
                    }
                }
            }
        }

        if (res.size()==0)
            res.add(Integer.parseInt(input));
        return res;
    }
}

[LeetCode] Pow(x, n)

Problem Statement (link):
Implement pow(x, n).

Analysis:
The naive approach is simply to multiply n x's together and get the result. The time complexity is O(n).

Thinking of a better way, when we do linear search with O(n), we optimize the time complexity to O(log(n)) using binary search. In this problem, we can do similar as well.

The following is an example for pow(3, 10), the 'res' is the result that we need to return. We initialize res = 1 so that res = res * x ^ n.
The strategy is to get x as large as possible by squaring it (n>>1 at the same time) so that when we multiple res and x, we have less operations. When n is odd and we couldn't do that, we change res = res*n, so that n = n-1 and n is even again.

Step	res	x	n
1	1	3	10
2	1	9	5
3	9	9	4
4	9	81	2
5	9	6561	1

Code:

public class Solution {
    public double myPow(double x, int n) {
        if (n==0) return 1;
        if (x==0 || x==1) return x;
        if (n<0) {
            x = 1/x;
            n = -n;
        }
        double res = 1;
        while (n>0) {
            if (n%2==1) {
                res *= x;
                n--;
            } else {
                x *= x;
                n >>= 1;
            }
        }
        return res;
    }
}

Further, we could optimize the above if-else statement inside the while loop such that we are able to skip one operations - from Step 2->Step 4. The code looks like following

public class Solution {
    public double myPow(double x, int n) {
        if (n==0) return 1;
        if (x==0 || x==1) return x;
        if (n<0) {
            x = 1/x;
            n = -n;
        }
        double res = 1;
        while (n>0) {
            if (n%2==1) {
                res *= x;
            }
            x *= x;
            n >>= 1;
        }
        return res;
    }
}

Java Autoboxing and unboxing

Autoboxing: Java converts primitive types to its wrapper class when object is expected;

Unboxing: Java converts the object to its primitive type value when primitive type is expected.

Details here.

Primitive type	Wrapper class
boolean	Boolean
byte	Byte
char	Character
float	Float
int	Integer
long	Long
short	Short
double	Double