Question

Formatted question description: https://leetcode.ca/all/241.html

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.

The test cases are generated such that the output values fit in a 32-bit integer and the number of different results does not exceed 10⁴.

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].

Algorithm

The solution employs a Divide and Conquer approach facilitated by recursion and is optimized with memoization through Python’s @cache decorator from the functools module.

Understanding the Approach

Base Case: If the input expression exp is purely numeric (contains no operators), it is directly converted to an integer and returned as a list containing this single number. This serves as the base case for the recursion.
Recursive Case: If the expression contains operators ('-', '+', '*'), the code iterates through the expression, looking for these operators. When an operator is found, the expression is split into two parts:
- left: The sub-expression before the operator.
- right: The sub-expression after the operator.
Recursive calls are made to compute the possible results from both the left and right sub-expressions separately.
Combining Results: For each pair of results from the left and right sub-expressions, the corresponding operation is applied based on the current operator c. The results of these operations are collected into the list ans.
Memoization with @cache: To optimize the solution, the @cache decorator is used. This decorator automatically stores the results of expensive function calls and returns the cached result when the same inputs occur again. This is particularly useful here because the same sub-expression might be evaluated multiple times due to different splits of the original expression. Memoization ensures that each unique sub-expression is only evaluated once, significantly reducing the computational overhead.

Example

Given the expression "2-1-1":

The function will first check and find that it’s not purely numeric.
It will then find the first -, split the expression into left = "2" and right = "1-1", and compute recursively.
- The left part results in [2].
- The right part, "1-1", is further split into left = "1" and right = "1" at the - operator, each resulting in [1]. Combining them with - gives [0].
The results from the left and right parts of the original split are combined using the - operator, resulting in [2 - 0] = [2].

For expressions with multiple operations, the function will explore all possible ways of splitting the expression around operators, recursively solve for each part, and combine the results, thereby considering all possible orderings of operations due to the non-associative property of subtraction and division.

Code

import java.util.ArrayList;
import java.util.List;

public class Different_Ways_to_Add_Parentheses {


    public class Solution {
        public List<Integer> diffWaysToCompute(String input) {
            List<Integer> result = new ArrayList<>();

            if (input == null || input.length() == 0) {
                return result;
            }

            for (int i = 0; i < input.length(); i++) {
                char c = input.charAt(i);

                if (!isOperator(c)) {
                    continue;
                }

                List<Integer> left = diffWaysToCompute(input.substring(0, i));
                List<Integer> right = diffWaysToCompute(input.substring(i + 1));

                for (int num1 : left) {
                    for (int num2 : right) {
                        int val = calculate(num1, num2, c);
                        result.add(val);
                    }
                }
            }

            // only contains one number
            if (result.isEmpty()) {
                result.add(Integer.parseInt(input));
            }

            return result;
        }

        private int calculate(int num1, int num2, char operator) {
            int result = 0;

            switch(operator) {
                case '+' : result = num1 + num2;
                    break;

                case '-' : result = num1 - num2;
                    break;

                case '*' : result = num1 * num2;
                    break;
            }

            return result;
        }

        private boolean isOperator(char operator) {
            return (operator == '+') || (operator == '-') || (operator == '*');
        }
    }
}

############

class Solution {
    private static Map<String, List<Integer>> memo = new HashMap<>();

    public List<Integer> diffWaysToCompute(String expression) {
        return dfs(expression);
    }

    private List<Integer> dfs(String exp) {
        if (memo.containsKey(exp)) {
            return memo.get(exp);
        }
        List<Integer> ans = new ArrayList<>();
        if (exp.length() < 3) {
            ans.add(Integer.parseInt(exp));
            return ans;
        }
        for (int i = 0; i < exp.length(); ++i) {
            char c = exp.charAt(i);
            if (c == '-' || c == '+' || c == '*') {
                List<Integer> left = dfs(exp.substring(0, i));
                List<Integer> right = dfs(exp.substring(i + 1));
                for (int a : left) {
                    for (int b : right) {
                        if (c == '-') {
                            ans.add(a - b);
                        } else if (c == '+') {
                            ans.add(a + b);
                        } else {
                            ans.add(a * b);
                        }
                    }
                }
            }
        }
        memo.put(exp, ans);
        return ans;
    }
}

class Solution {
public:
    vector<int> diffWaysToCompute(string expression) {
        return dfs(expression);
    }

    vector<int> dfs(string exp) {
        if (memo.count(exp)) return memo[exp];
        if (exp.size() < 3) return {stoi(exp)};
        vector<int> ans;
        int n = exp.size();
        for (int i = 0; i < n; ++i) {
            char c = exp[i];
            if (c == '-' || c == '+' || c == '*') {
                vector<int> left = dfs(exp.substr(0, i));
                vector<int> right = dfs(exp.substr(i + 1, n - i - 1));
                for (int& a : left) {
                    for (int& b : right) {
                        if (c == '-')
                            ans.push_back(a - b);
                        else if (c == '+')
                            ans.push_back(a + b);
                        else
                            ans.push_back(a * b);
                    }
                }
            }
        }
        memo[exp] = ans;
        return ans;
    }

private:
    unordered_map<string, vector<int>> memo;
};

class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        @cache # note
        def dfs(exp):
            if exp.isdigit():
                return [int(exp)] # return list
            ans = []
            for i, c in enumerate(exp):
                if c in '-+*':
                    left, right = dfs(exp[:i]), dfs(exp[i + 1 :])
                    for a in left:
                        for b in right:
                            if c == '-':
                                ans.append(a - b)
                            elif c == '+':
                                ans.append(a + b)
                            else:
                                ans.append(a * b)
            return ans

        return dfs(expression)

############

'''
>>> from operator import *
>>> add(1,2)
3
>>> sub(1,2)
-1
>>> mul(1,2)
2
>>> div(1,2)
0

### append() vs extend()

>>> x = [1, 2, 3]
>>> x.append([4, 5])
>>> print(x)
[1, 2, 3, [4, 5]]


>>> x = [1, 2, 3]
>>> x.extend([4, 5])
>>> print(x)
[1, 2, 3, 4, 5]


https://stackoverflow.com/questions/252703/what-is-the-difference-between-pythons-list-methods-append-and-extend
'''

from operator import *

class Solution(object):
  def diffWaysToCompute(self, input):
    """
    :type input: str
    :rtype: List[int]
    """
    ops = {"+": add, "-": sub, "*": mul, "/": div}
    ans = []
    for i, c in enumerate(input):
      if c in ops:
        left = self.diffWaysToCompute(input[:i])
        right = self.diffWaysToCompute(input[i + 1:])
        ans.extend([ops[c](a, b) for a in left for b in right])
    return ans if ans else [int(input)]

var memo = map[string][]int{}

func diffWaysToCompute(expression string) []int {
	return dfs(expression)
}

func dfs(exp string) []int {
	if v, ok := memo[exp]; ok {
		return v
	}
	if len(exp) < 3 {
		v, _ := strconv.Atoi(exp)
		return []int{v}
	}
	ans := []int{}
	for i, c := range exp {
		if c == '-' || c == '+' || c == '*' {
			left, right := dfs(exp[:i]), dfs(exp[i+1:])
			for _, a := range left {
				for _, b := range right {
					if c == '-' {
						ans = append(ans, a-b)
					} else if c == '+' {
						ans = append(ans, a+b)
					} else {
						ans = append(ans, a*b)
					}
				}
			}
		}
	}
	memo[exp] = ans
	return ans
}

using System.Collections.Generic;

public class Solution {
    public IList<int> DiffWaysToCompute(string input) {
        var values = new List<int>();
        var operators = new List<char>();
        var sum = 0;
        foreach (var ch in input)
        {
            if (ch == '+' || ch == '-' || ch == '*')
            {
                values.Add(sum);
                operators.Add(ch);
                sum = 0;
            }
            else
            {
                sum = sum * 10 + ch - '0';
            }
        }
        values.Add(sum);

        var f = new List<int>[values.Count, values.Count];
        for (var i = 0; i < values.Count; ++i)
        {
            f[i, i] = new List<int> { values[i] };
        }

        for (var diff = 1; diff < values.Count; ++diff)
        {
            for (var left = 0; left + diff < values.Count; ++left)
            {
                var right = left + diff;
                f[left, right] = new List<int>();
                for (var i = left; i < right; ++i)
                {
                    foreach (var leftValue in f[left, i])
                    {
                        foreach (var rightValue in f[i + 1, right])
                        {
                            switch (operators[i])
                            {
                                case '+':
                                    f[left, right].Add(leftValue + rightValue);
                                    break;
                                case '-':
                                    f[left, right].Add(leftValue - rightValue);
                                    break;
                                case '*':
                                    f[left, right].Add(leftValue * rightValue);
                                    break;
                            }
                        }
                    }
                }
            }
        }

        return f[0, values.Count - 1];
    }
}

241 - Different Ways to Add Parentheses

Question

Algorithm

Understanding the Approach

Example

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Understanding the Approach

Example

Code

All Problems

All Solutions