241. Different Ways to Add Parentheses LeetCode Solution

In this guide, you will get 241. Different Ways to Add Parentheses LeetCode Solution with the best time and space complexity. The solution to Different Ways to Add Parentheses problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Different Ways to Add Parentheses solution in C++
4. Different Ways to Add Parentheses solution in Java
5. Different Ways to Add Parentheses solution in Python
6. Additional Resources

Problem Statement of 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.

Complexity Analysis

• Time Complexity: O(2^n)
• Space Complexity: O(n \cdot 2^n)

241. Different Ways to Add Parentheses LeetCode Solution in C++

class Solution {
 public:
  vector<int> diffWaysToCompute(string expression) {
    return ways(expression, {});
  }

 private:
  vector<int> ways(const string& s, unordered_map<string, vector<int>>&& mem) {
    if (const auto it = mem.find(s); it != mem.cend())
      return it->second;

    vector<int> ans;

    for (int i = 0; i < s.length(); ++i)
      if (ispunct(s[i]))
        for (const int a : ways(s.substr(0, i), std::move(mem)))
          for (const int b : ways(s.substr(i + 1), std::move(mem)))
            if (s[i] == '+')
              ans.push_back(a + b);
            else if (s[i] == '-')
              ans.push_back(a - b);
            else
              ans.push_back(a * b);

    return mem[s] = (ans.empty() ? vector<int>{stoi(s)} : ans);
  }
};
/* code provided by PROGIEZ */

241. Different Ways to Add Parentheses LeetCode Solution in Java

class Solution {
  public List<Integer> diffWaysToCompute(String expression) {
    return ways(expression, new HashMap<>());
  }

  private List<Integer> ways(final String s, Map<String, List<Integer>> mem) {
    if (mem.containsKey(s))
      return mem.get(s);

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

    for (int i = 0; i < s.length(); ++i)
      if (!Character.isDigit(s.charAt(i)))
        for (final int a : ways(s.substring(0, i), mem))
          for (final int b : ways(s.substring(i + 1), mem))
            if (s.charAt(i) == '+')
              ans.add(a + b);
            else if (s.charAt(i) == '-')
              ans.add(a - b);
            else
              ans.add(a * b);

    if (ans.isEmpty()) { // Single number
      mem.put(s, Arrays.asList(Integer.parseInt(s)));
      return mem.get(s);
    }
    mem.put(s, ans);
    return ans;
  }
}
// code provided by PROGIEZ

241. Different Ways to Add Parentheses LeetCode Solution in Python

class Solution:
  @functools.lru_cache(None)
  def diffWaysToCompute(self, expression: str) -> list[int]:
    ans = []

    for i, c in enumerate(expression):
      if c in '+-*':
        for a in self.diffWaysToCompute(expression[:i]):
          for b in self.diffWaysToCompute(expression[i + 1:]):
            ans.append(eval(str(a) + c + str(b)))

    return ans or [int(expression)]
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.