Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

241. Different Ways to Add Parentheses

Time: $O(2^n)$

Space: $O(n \cdot 2^n)$

			


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

 private:
  vector<int> ways(const string& s, unordered_map<string, vector<int>>&& memo) {
    if (memo.count(s))
      return memo[s];

    vector<int> ans;

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

    return memo[s] = (ans.empty() ? vector<int>{stoi(s)} : ans);
  }
};




			


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

  private List<Integer> ways(final String s, Map<String, List<Integer>> memo) {
    if (memo.containsKey(s))
      return memo.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), memo))
          for (final int b : ways(s.substring(i + 1), memo))
            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
      memo.put(s, Arrays.asList(Integer.parseInt(s)));
      return memo.get(s);
    }
    memo.put(s, ans);
    return ans;
  }
}




			


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