241. Different Ways to Add Parentheses

二刷 07/2022

Version #1 Recursion

看起来是medium的题结果竟然没做出来

一开始写了好久都写不对，我自己的写法是在recursion里面一直expand当前的值，然后和后面subresult的结果combine在一起，这里的问题是

((2*(3-4))*5) = -10 

(2*((3-4)*5)) = -10 

里面的 ((2*(3-4))*5) 永远都不会被算到，因为前半部分永远是顺序的2 * 3 - 4

正确做法是每次把当前string分成operator的左右两半

Time - 感觉outer loop应该是所有substring遍历一遍的复杂度，就是O(N^2), inner loop是substring O(N)另外还有iterate over two sub lists to compute their combination results O(N^2)所以大概是O(n^4)?

Space O(N^2) for all substrings

Runtime: 2 ms, faster than 92.07% of Java online submissions for Different Ways to Add Parentheses.

Memory Usage: 41.8 MB, less than 94.00% of Java online submissions for Different Ways to Add Parentheses.

class Solution {

    public List<Integer> diffWaysToCompute(String expression) {

        return compute(expression, new HashMap<>());

    }

    

    private List<Integer> compute(String exp, Map<String, List<Integer>> mem) {

        if (mem.containsKey(exp)) {

            return mem.get(exp);

        }

        boolean isNum = true;

        List<Integer> result = new ArrayList<>();

        for (int i = 0; i < exp.length(); i++) {

            if (!Character.isDigit(exp.charAt(i))) {

                isNum = false;

                List<Integer> res1 = compute(exp.substring(0, i), mem);

                List<Integer> res2 = compute(exp.substring(i + 1), mem);

                for (int num1 : res1) {

                    for (int num2 : res2) {

                        switch (exp.charAt(i)) {

                            case '+':

                                result.add(num1 + num2);

                                continue;

                            case '-':

                                result.add(num1 - num2);

                                continue;

                            case '*':

                                result.add(num1 * num2);

                        }

                    }

                }

            }

        }

        if (isNum) {

            result.add(Integer.valueOf(exp));

        }

        mem.put(exp, result);

        return result;

    }

}

一刷

Add parentheses means give different priority to each operator
char to integer: c - '0'
这里用isDigit来标记是不是纯数字，也可以在最后看subResult.size() == 0，表明也是digit

83.50 %

public class Solution {
    public List<Integer> diffWaysToCompute(String input) {
        if (input == null || input.length() == 0) return new ArrayList<Integer>();
        //TODO
        return diffWaysToCompute(input.toCharArray(), 0, input.length() - 1);
     
    }
    private void compute(char operator, List<Integer> subResult, List<Integer> left, List<Integer> right) {
        for (Integer n1 : left) {
            for (Integer n2 : right) {
                if (operator == '-') subResult.add(n1 - n2);
                if (operator == '+') subResult.add(n1 + n2);
                if (operator == '*') subResult.add(n1 * n2);
            }
        }
    }
    private List<Integer> diffWaysToCompute(char[] str, int start, int end) {
        List<Integer> subResult = new ArrayList<>();
     
        if (start > end) return subResult;
     
        boolean isDigit = true;
        for (int i = start; i <= end; i++) {
            if (str[i] == '+' || str[i] == '-' || str[i] == '*') {
                isDigit = false;
                List<Integer> left = diffWaysToCompute(str, start, i - 1);
                List<Integer> right = diffWaysToCompute(str, i + 1, end);
                compute(str[i], subResult, left, right);
            }
        }
        if (isDigit) {
            int digit = 0;
            for (int i = start; i <= end; i++) {
                digit = digit * 10 + str[i] - '0';
            }
            subResult.add(digit);
        }
        return subResult;
    }
}