Java Solution + Lesson Learned


  • 0
    Y

    I think the input assumes that there's no negative values between each operator, and the first number is positive.

    (Bad approach) My first attempt was to use a top-down approach, recursively computing parts of the input string and put the partial results back. For example, in string "a+b*c-d", iterate over the string to compute partial results. First compute a+b = e and put e back, so we get e*c-d, and then recurse. After that, compute b*c = f and put it back, so we get a+f-d and then recurse. Similarly compute c-d and recurse. The problem with this approach is that whenever the partial result is negative, then we have a ton of special cases to handle, which makes it extremely hard to code correct. For example, "2*1-3", when we compute 1-3 = -2 and put it back, the string becomes 2*-2, and I have to write extra code to handle the special case where there are two consecutive operators. I found a better way to resolve this operator issue is to put the input string, with each number and operator separated, into an Object array. It's still hard to code tho, and I won't bother writing it down.

    I didn't realize a bottom-up approach (which is actually very obvious) before I read some posts. The idea of store all possible results from the left and right of an operator, and then use loop to compute permutations, makes it super easy to code.

    public class Solution {
        private String ops = "+-*";
        
        public List<Integer> diffWaysToCompute(String input) {
            List<Integer> L = new ArrayList<>();
            if (input.length() == 0) {
                return L;
            }
            if (!input.contains("+") && !input.contains("-") && !input.contains("*")) {
                L.add(Integer.parseInt(input));
                return L;
            }
            for (int i = 0; i < input.length(); i++) {
                if (isOperator(input.charAt(i))) {
                    List<Integer> left = diffWaysToCompute(input.substring(0,i));
                    List<Integer> right = diffWaysToCompute(input.substring(i+1));
                    for (int j = 0; j < left.size(); j++) {
                        for (int k = 0; k < right.size(); k++) {
                            L.add(compute(left.get(j), right.get(k), input.charAt(i)));
                        }
                    }
                }
            }
            return L;
        }
        
        private int compute(int a, int b, char op) {
            switch (op) {
                case '+':
                    return a + b;
                case '-':
                    return a - b;
                case '*':
                    return a * b;
                default:
                    throw new IllegalArgumentException("Operator error");
            }
        }
        
        private boolean isOperator(char c) {
            return ops.indexOf(c) != -1;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.