Skip to content

Latest commit

 

History

History
 
 

241

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
README.md
README.md
 
 

README.md

241. Different Ways to Add Parentheses (Medium)

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.

 

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

Companies:
Facebook, Bloomberg, Samsung

Related Topics:
Math, String, Dynamic Programming, Recursion, Memoization

Similar Questions:

Solution 1. Divide And Conquer (+ Memoization)

Tip: find the pattern of the length of output given N operators in input.

0 1 2 3 4 ...
1 1 2 5 14 ...

This is a Catalan Number Sequence. For this sequence, it's very likely that you can use "Divide and Conquer" -- separating the input as two parts, solve the subproblem of the smaller parts and merge them.

For each operator, use it to separate the expression into two parts. Compute the diffWaysToCompute for both the left and right parts, and merge the results.

We can optionally add memoization to avoid computing the same expression multiple times.

// OJ: https://leetcode.com/problems/different-ways-to-add-parentheses/
// Author: github.com/lzl124631x
// Time: O(S * C(N))
//          where S is the length of `input`,
//          N is the count of operators in `input` and C(N) is the Nth Catalan Number
// Space: O(S * SUM( C(i) | 1 <= i <= N ))
class Solution {
    unordered_map<string, vector<int>> m;
public:
    vector<int> diffWaysToCompute(string s) {
        if (m.count(s)) return m[s];
        vector<int> ans;
        for (int i = 0; i < s.size(); ++i) {
            if (isdigit(s[i])) continue;
            auto A = diffWaysToCompute(s.substr(0, i));
            auto B = diffWaysToCompute(s.substr(i + 1));
            for (int a : A) {
                for (int b : B) {
                    switch (s[i]) {
                        case '+': ans.push_back(a + b); break;
                        case '-': ans.push_back(a - b); break;
                        case '*': ans.push_back(a * b); break;
                    }
                }
            }
        }
        return m[s] = ans.size() ? ans : vector<int>{stoi(s)};
    }
};

Discuss

https://leetcode.com/problems/different-ways-to-add-parentheses/discuss/303491/C++-O(C(N))-Divide-and-Conquer-with-tipexplanation