SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

Given a string expression containing digits and operators (+, -, *), this function computes all possible results by evaluating the expression in different ways with different parenthesizations. The function should return a list of all possible results.

Intuition

To solve this problem, you need to consider all possible ways to parenthesize the given expression. For each operator in the expression, split the expression into left and right subexpressions and recursively compute the results for each subexpression. Combine the results of the left and right subexpressions based on the operator to get all possible results for the original expression.

Approach

1. Recursive Computation:

   • Use a recursive function to evaluate all possible ways of parenthesizing the expression. For each operator in the expression, split the expression into left and right parts.
   • Recursively compute results for the left and right parts.
   • Combine results from the left and right parts based on the operator to get all possible results.

2. Memoization:

   • Use memoization to store results of previously computed subexpressions to avoid redundant calculations and optimize performance.

3. Base Case:

   • If the expression is a single number, return that number as the result.

Complexity

Time Complexity:

The time complexity is O(2^n) where n is the length of the expression. This is because in the worst case, each operator could lead to exponential branching in the recursive calls.

Space Complexity:

The space complexity is O(n) due to the use of memoization and the recursion stack. Memoization helps store results of subexpressions to avoid redundant computations.

Code

C++

class Solution {
private:
    unordered_map<string, vector<int>> memo;

    vector<int> compute(const string& expr) {
        // Check memoization
        if (memo.find(expr) != memo.end()) {
            return memo[expr];
        }

        vector<int> result;

        // Check if expr is a single number
        if (isdigit(expr[0]) || (expr[0] == '-' && isdigit(expr[1]))) {
            result.push_back(stoi(expr));
            return result;
        }

        // Iterate through the expression
        for (size_t i = 0; i < expr.length(); ++i) {
            char op = expr[i];
            if (op == '+' || op == '-' || op == '*') {
                // Compute results of the left and right parts
                string leftExpr = expr.substr(0, i);
                string rightExpr = expr.substr(i + 1);

                vector<int> leftResults = compute(leftExpr);
                vector<int> rightResults = compute(rightExpr);

                // Combine results from left and right parts
                for (int left : leftResults) {
                    for (int right : rightResults) {
                        if (op == '+') result.push_back(left + right);
                        else if (op == '-') result.push_back(left - right);
                        else if (op == '*') result.push_back(left * right);
                    }
                }
            }
        }

        memo[expr] = result;
        return result;
    }

public:
    vector<int> diffWaysToCompute(string expression) {
        return compute(expression);
    }
};

Python

class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        @lru_cache(None)
        def compute(expr: str) -> List[int]:
            if expr.isdigit() or (expr[0] == '-' and expr[1:].isdigit()):  # Check if expr is a number
                return [int(expr)]

            result = []

            for i, char in enumerate(expr):
                if char in '+-*':
                    left_results = compute(expr[:i])
                    right_results = compute(expr[i + 1:])
                    
                    for left in left_results:
                        for right in right_results:
                            if char == '+':
                                result.append(left + right)
                            elif char == '-':
                                result.append(left - right)
                            elif char == '*':
                                result.append(left * right)

            return result
        
        return compute(expression)

Java

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

    public List<Integer> diffWaysToCompute(String expression) {
        if (memo.containsKey(expression)) {
            return memo.get(expression);
        }

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

        if (expression.matches("-?\\d+")) { // Check if expression is a number
            result.add(Integer.parseInt(expression));
            return result;
        }

        for (int i = 0; i < expression.length(); i++) {
            char op = expression.charAt(i);
            if (op == '+' || op == '-' || op == '*') {
                String leftExpr = expression.substring(0, i);
                String rightExpr = expression.substring(i + 1);

                List<Integer> leftResults = diffWaysToCompute(leftExpr);
                List<Integer> rightResults = diffWaysToCompute(rightExpr);

                for (int left : leftResults) {
                    for (int right : rightResults) {
                        if (op == '+') result.add(left + right);
                        else if (op == '-') result.add(left - right);
                        else if (op == '*') result.add(left * right);
                    }
                }
            }
        }

        memo.put(expression, result);
        return result;
    }
}

JavaScript

var diffWaysToCompute = function (expression) {

    function compute() {
        if (Number.isInteger(Number(expression))) {
            return [Number(expression)];
        }

        let result = [];

        if (memo[expression]) {
            return memo[expression];
        }

        for (let i = 0; i < expression.length; i++) {
            let operator = expression[i];

            if (Number.isNaN(Number(operator))) {
                let leftResults = diffWaysToCompute(expression.slice(0, i));
                let rightResults = diffWaysToCompute(expression.slice(i + 1));

                for (let left of leftResults) {
                    for (let right of rightResults) {
                        result.push(
                            operator === '+'
                                ? left + right
                                : operator === '-'
                                    ? left - right
                                    : left * right
                        );
                    }
                }
            }
        }
        memo[expression] = result;
        return result;
    }

    let memo = {};
    return compute();
};