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

For each operator, divide the input into two parts, left and right, and throw them into recursion to calculate, so you can get two integer arrays left and right, which represent all that can be obtained by adding different parentheses to the two parts’ different values.

At this point, we only need to take numbers from the two arrays to perform the current operator calculation, and then save in the result.

Of course, if the final result res is still empty, then there is only one case, input itself is a number, directly converted to an integer and stored in the result.

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
        def dfs(exp):
            if exp.isdigit():
                return [int(exp)]
            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 *


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

'''
>>> 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
'''

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

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions