algoadvance

Leetcode 241. Different Ways to Add Parentheses

Problem Statement

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators using parentheses. The valid operators are +, -, and *.

Example

Input: "2-1-1"
Output: [0, 2]

Explanation:

((2-1)-1) = 0 
(2-(1-1)) = 2

Input: "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

Clarifying Questions

  1. Does the string always contain only digits and the operators +, -, *?
    • Yes, the input string will only contain non-negative integers and the operators +, -, *.
  2. Are there any constraints on the length of the input string?
    • The length of the input string is guaranteed to be less than or equal to 20.

Strategy

We will solve this problem using a divide and conquer method with memoization. The idea is to:

  1. Parse the input string.
  2. Recursively separate the string at each operator and solve the subproblems.
  3. Combine the results of subproblems according to the operator.

The key steps include:

Code

Here is the implementation in C++:

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

using namespace std;

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

    vector<int> diffWaysToComputeHelper(string input) {
        if (memo.find(input) != memo.end()) {
            return memo[input];
        }

        vector<int> result;

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

                vector<int> leftResults = diffWaysToComputeHelper(leftPart);
                vector<int> rightResults = diffWaysToComputeHelper(rightPart);

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

        if (result.empty()) {
            result.push_back(stoi(input));
        }

        memo[input] = result;
        return result;
    }

public:
    vector<int> diffWaysToCompute(string input) {
        return diffWaysToComputeHelper(input);
    }
};

Time Complexity

The time complexity of this solution is challenging to analyze precisely because it depends on the number of operators and the recursive splits. However, it can be considered roughly exponential in the number of operators due to the number of recursive calls.

In general, the solution works efficiently within the given constraints by leveraging memoization to avoid redundant computations. Memoization helps in caching results of subproblems and thus reduces the overhead significantly.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI