241. Different Ways to Add Parentheses

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

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].
• The integer values in the input expression do not have a leading '-' or '+' denoting the sign.

Approach 01:

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>

class Solution {
 public:
    std::vector<int> diffWaysToCompute(const std::string& expression) {
        return computeWays(expression, {});
    }

 private:
    std::vector<int> computeWays(const std::string& expression, std::unordered_map<std::string, std::vector<int>>&& memoization) {
        if (const auto it = memoization.find(expression); it != memoization.cend()){
            return it->second;
        }

    std::vector<int> results;

    for (int index = 0; index < expression.length(); ++index)
        if (ispunct(expression[index]))
            for (const int leftPart : computeWays(expression.substr(0, index), std::move(memoization)))
                for (const int rightPart : computeWays(expression.substr(index + 1), std::move(memoization)))
                    if (expression[index] == '+')
                        results.push_back(leftPart + rightPart);
                    else if (expression[index] == '-')
                        results.push_back(leftPart - rightPart);
                    else
                        results.push_back(leftPart * rightPart);

    return memoization[expression] = (results.empty() ? std::vector<int>{std::stoi(expression)} : results);
    }
};

class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        return self.computeWays(expression, {})

    def computeWays(self, expression: str, memoization: dict):
        if expression in memoization:
            return memoization[expression]

        results = []

        for index in range(len(expression)):
            if expression[index] in "+-*":
                leftResults = self.computeWays(expression[:index], memoization)
                rightResults = self.computeWays(expression[index + 1:], memoization)

                for leftPart in leftResults:
                    for rightPart in rightResults:
                        if expression[index] == '+':
                            results.append(leftPart + rightPart)
                        elif expression[index] == '-':
                            results.append(leftPart - rightPart)
                        else:
                            results.append(leftPart * rightPart)

        if not results:
            results.append(int(expression))

        memoization[expression] = results
        return results

Time Complexity

• Recursive splitting of the expression:

  The function splits the expression at every operator (`+`, `-`, `*`) and recursively computes all possible results from both the left and right subexpressions. This creates a recursion tree where at each node, the string is split into two subproblems.

• Number of subproblems:

  The number of possible subexpressions grows exponentially. Each expression can be split in multiple ways, and the total number of possible subexpressions is \(O(2^n)\), where \(n\) is the number of operators in the expression.

• Memoization optimization:

  The algorithm uses memoization to store and reuse results for already computed subexpressions, which helps avoid recalculating the same subexpression multiple times. The time complexity with memoization is reduced to \(O(n^3)\), where \(n\) is the length of the expression. This is because each split generates a recursive call, and the total number of unique subexpressions is \(O(n^2)\). Each recursive call performs \(O(n)\) work to evaluate the expression.

• Overall Time Complexity:

  The overall time complexity is \(O(n^3)\), considering the number of recursive calls and memoization.

Space Complexity

• Space for memoization:

  The memoization map stores the results for each unique subexpression, and the number of unique subexpressions is \(O(n^2)\). Each entry in the map can store multiple results, but in the worst case, each subexpression contributes one result. Therefore, the space complexity for memoization is \(O(n^3)\).

• Recursive call stack:

  The depth of the recursion tree is proportional to the number of operators in the expression, leading to a maximum recursion depth of \(O(n)\), where \(n\) is the length of the expression. This adds an additional space complexity of \(O(n)\).

• Overall Space Complexity:

  The overall space complexity is \(O(n^3)\) due to memoization, plus the \(O(n)\) recursion depth, which is dominated by the memoization size.