241. Different Ways to Add Parentheses

Created: 9/29/2021

Leetcode

Given a string expression of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. You may return the answer in any order.

Example 1:

Input: expression = "2-1-1"
Output: [0,2]
Explanation:
((2-1)-1) = 0 
(2-(1-1)) = 2

Example 2:

Input: expression = "2*3-4*5"
Output: [-34,-14,-10,-10,10]
Explanation:
(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

Constraints:

• 1 <= expression.length <= 20

• expression consists of digits and the operator '+', '-', and '*'.

• All the integer values in the input expression are in the range [0, 99].

Basic Idea:

因为可以任意加括号，事实上在计算的时候我们不需要关心四则运算的优先顺序。所谓随便加括号，我们可以使用分治的思路，使用DFS来做。每层我们考虑给定左右边界内的部分，选择一个中间的分界线(一个符号)，递归求分界线两边的所有可能的值，然后对于左右两边的值两两计算分界线处的符号。整个时间复杂度大概是位于 O(2^n) ，因为这是所有可能加括号的位置的可能性，但由于括号总是成对出现，实际上的时间复杂度略有出入。

Java Code:

class Solution {
    public List<Integer> diffWaysToCompute(String expression) {
        List<Character> ops = new ArrayList<>();
        List<Integer> numbers = new ArrayList<>();
        for (int i = 0; i < expression.length(); ++i) {
            char c = expression.charAt(i);
            if (!isDigit(c)) {
                ops.add(c);
            } else {
                int num = 0;
                int j = i;
                while (j < expression.length()) {
                    char cj = expression.charAt(j);
                    if (isDigit(cj)) {
                        num = num * 10 + cj - '0';
                        if (j == expression.length() - 1) {
                            numbers.add(num);
                            j++;
                        }
                    } else {
                        numbers.add(num);
                        break;
                    }
                    j++;
                }
                i = j - 1;
            }
        }
        if (ops.isEmpty()) {
            return numbers;
        }
        return dfs(ops, numbers, 0, numbers.size() - 1);
    }
    
    private List<Integer> dfs(List<Character> ops, List<Integer> numbers, int left, int right) {
        if (left == right) {
            return Arrays.asList(numbers.get(left));
        }
        List<Integer> ret = new ArrayList<>();
        for (int i = left; i < right; ++i) {
            char op = ops.get(i);
            List<Integer> leftResList = dfs(ops, numbers, left, i);
            List<Integer> rightResList = dfs(ops, numbers, i + 1, right);
            for (int leftRes : leftResList) {
                for (int rightRes : rightResList) {
                    ret.add(eval(op, leftRes, rightRes));
                }
            }
        }
        return ret;
    }
    
    private int eval(char op, int a, int b) {
        if (op == '+') return a + b;
        if (op == '-') return a - b;
        if (op == '*') return a * b;
        if (op == '/') return a / b;
        else return Integer.MAX_VALUE;
    }
    
    private boolean isDigit(char c) {
        return '0' <= c && c <= '9';
    }
}