Sponsored
Sponsored
The problem can be approached by using recursion to divide the expression into sub-expressions at each operator, evaluating each possible combination. For each operator, compute the left and right sub-expressions separately, then combine their results based on the operator. This allows us to explore all possible ways to parenthesize the expression and evaluate it.
Time Complexity: O(2^n) - In the worst case, the algorithm evaluates every partition.
Space Complexity: O(2^n) - due to the recursion depth and storage of intermediate results.
1import java.util.*;
2
3public class Solution {
4 public List<Integer> diffWaysToCompute(String expression) {
5 List<Integer> results = new ArrayList<>();
6 for (int i = 0; i < expression.length(); i++) {
7 char c = expression.charAt(i);
8 if (c == '+' || c == '-' || c == '*') {
9 List<Integer> left = diffWaysToCompute(expression.substring(0, i));
10 List<Integer> right = diffWaysToCompute(expression.substring(i + 1));
11
12 for (int l : left) {
13 for (int r : right) {
14 switch (c) {
15 case '+': results.add(l + r); break;
16 case '-': results.add(l - r); break;
17 case '*': results.add(l * r); break;
18 }
19 }
20 }
21 }
22 }
23 if (results.isEmpty()) {
24 results.add(Integer.parseInt(expression));
25 }
26 return results;
27 }
28
29 public static void main(String[] args) {
30 Solution sol = new Solution();
31 System.out.println(sol.diffWaysToCompute("2*3-4*5"));
32 }
33}The Java solution adopts a similar recursive strategy using ArrayLists to store intermediate results. It identifies operators in the expression, divides the expression into left and right parts recursively, and calculates possible results for each operator using switch-case logic. If no operators are found, it returns the number.
To optimize the recursive approach, we can use memoization to cache the results of subproblems. This avoids redundant evaluations of the same sub-expressions, thereby optimizing the time complexity. We store results of sub-expressions in a hash map and reuse them when the same sub-expression is encountered again.
Time Complexity: O(n^3) - n^2 subproblems with evaluation cost per subproblem.
Space Complexity: O(n^2) - for storing results of subproblems in a memoization table.
1import java.util.*;
2
3
The Java version applies memoization by storing results of already computed sub-expressions in a HashMap. It checks for cached results before computing new ones, ensuring no duplicate calculations for the same expression parts. This optimization reduces the time complexity significantly compared to the naive recursive approach.