The Indian Engineer

Problem 241 Different Ways to Add Parentheses

Posted on 6 mins

Math String Dynamic-Programming Recursion Memoization

Table of Contents

Problem Statement

Link - Problem 241

Question

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:

Solution 

class Solution {
public:
    vector<int> diffWaysToCompute(string expression) {
        std::ios::sync_with_stdio(false);
        unordered_map<string, vector<int>> memo;
        return computeWithMemo(expression, memo);
    }

private:
    vector<int> computeWithMemo(const string& expression, unordered_map<string, vector<int>>& memo) {
        if (memo.find(expression) != memo.end()) {
            return memo[expression];
        }

        vector<int> results;
        for (int i = 0; i < expression.size(); ++i) {
            char c = expression[i];
            if (c == '+' || c == '-' || c == '*') {
                string leftPart = expression.substr(0, i);
                string rightPart = expression.substr(i + 1);

                vector<int> leftResults = computeWithMemo(leftPart, memo);
                vector<int> rightResults = computeWithMemo(rightPart, memo);

                for (int left : leftResults) {
                    for (int right : rightResults) {
                        if (c == '+') {
                            results.push_back(left + right);
                        } else if (c == '-') {
                            results.push_back(left - right);
                        } else if (c == '*') {
                            results.push_back(left * right);
                        }
                    }
                }
            }
        }

        if (results.empty()) {
            results.push_back(stoi(expression));
        }

        memo[expression] = results;
        return results;
    }
};

Complexity Analysis 

| Algorithm                           | Time Complexity | Space Complexity |
| ----------------------------------- | --------------- | ---------------- |
| Divide and Conquer with Memoization | O(2^n)          | O(n)             |

Explanation

Intial Thoughts

The problem can be approached by breaking down the given expression into smaller sub-expressions and applying operators in different ways. We should consider the types of operators and their positions within the expression, thinking about how they can be evaluated in different orders. The recursive nature of this problem suggests that a divide-and-conquer strategy may be effective, allowing us to solve sub-problems and combine their results. Additionally, we should think about how to avoid redundant computations and optimize the solution process.

Intuitive Analysis

To solve this problem intuitively, think of the expression as a tree, where each operator is a node that splits the expression into smaller sub-expressions. We can then imagine all possible ways to evaluate this tree, considering each operator in turn and how it affects the overall result. This can be done recursively, where for each operator, we solve the sub-problems on either side of it and combine their results. It’s also important to consider using a memoization strategy to store the results of sub-problems and avoid redundant computations, which can greatly improve the efficiency of the solution.

1. Intuition

2. Implementation

Complexity Analysis

Time Complexity:

Space Complexity:

Footnote

This question is rated as Medium difficulty.

Similar Questions:

Title URL Difficulty
Unique Binary Search Trees II https://leetcode.com/problems/unique-binary-search-trees-ii Medium
Basic Calculator https://leetcode.com/problems/basic-calculator Hard
Expression Add Operators https://leetcode.com/problems/expression-add-operators Hard
The Score of Students Solving Math Expression https://leetcode.com/problems/the-score-of-students-solving-math-expression Hard
Minimize Result by Adding Parentheses to Expression https://leetcode.com/problems/minimize-result-by-adding-parentheses-to-expression Medium