Skip to content

241. Different Ways to Add Parentheses 👍

  • Time: $O(2^n)$
  • Space: $O(n \cdot 2^n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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)]