241 - Different Ways to Add Parentheses

 C++

• class Solution {
  public:
      vector<int> diffWaysToCompute(string expression) {
          return dfs(expression);
      }
  
      vector<int> dfs(string exp) {
          if (memo.count(exp)) return memo[exp];
          if (exp.size() < 3) return {stoi(exp)};
          vector<int> ans;
          int n = exp.size();
          for (int i = 0; i < n; ++i) {
              char c = exp[i];
              if (c == '-' || c == '+' || c == '*') {
                  vector<int> left = dfs(exp.substr(0, i));
                  vector<int> right = dfs(exp.substr(i + 1, n - i - 1));
                  for (int& a : left) {
                      for (int& b : right) {
                          if (c == '-')
                              ans.push_back(a - b);
                          else if (c == '+')
                              ans.push_back(a + b);
                          else
                              ans.push_back(a * b);
                      }
                  }
              }
          }
          memo[exp] = ans;
          return ans;
      }
  
  private:
      unordered_map<string, vector<int>> memo;
  };

JAVA

• import java.util.ArrayList;
  import java.util.List;
  
  public class Different_Ways_to_Add_Parentheses {
  
  
      public class Solution {
          public List<Integer> diffWaysToCompute(String input) {
              List<Integer> result = new ArrayList<>();
  
              if (input == null || input.length() == 0) {
                  return result;
              }
  
              for (int i = 0; i < input.length(); i++) {
                  char c = input.charAt(i);
  
                  if (!isOperator(c)) {
                      continue;
                  }
  
                  List<Integer> left = diffWaysToCompute(input.substring(0, i));
                  List<Integer> right = diffWaysToCompute(input.substring(i + 1));
  
                  for (int num1 : left) {
                      for (int num2 : right) {
                          int val = calculate(num1, num2, c);
                          result.add(val);
                      }
                  }
              }
  
              
              if (result.isEmpty()) {
                  result.add(Integer.parseInt(input));
              }
  
              return result;
          }
  
          private int calculate(int num1, int num2, char operator) {
              int result = 0;
  
              switch(operator) {
                  case '+' : result = num1 + num2;
                      break;
  
                  case '-' : result = num1 - num2;
                      break;
  
                  case '*' : result = num1 * num2;
                      break;
              }
  
              return result;
          }
  
          private boolean isOperator(char operator) {
              return (operator == '+') || (operator == '-') || (operator == '*');
          }
      }
  }
  
  ############
  
  class Solution {
      private static Map<String, List<Integer>> memo = new HashMap<>();
  
      public List<Integer> diffWaysToCompute(String expression) {
          return dfs(expression);
      }
  
      private List<Integer> dfs(String exp) {
          if (memo.containsKey(exp)) {
              return memo.get(exp);
          }
          List<Integer> ans = new ArrayList<>();
          if (exp.length() < 3) {
              ans.add(Integer.parseInt(exp));
              return ans;
          }
          for (int i = 0; i < exp.length(); ++i) {
              char c = exp.charAt(i);
              if (c == '-' || c == '+' || c == '*') {
                  List<Integer> left = dfs(exp.substring(0, i));
                  List<Integer> right = dfs(exp.substring(i + 1));
                  for (int a : left) {
                      for (int b : right) {
                          if (c == '-') {
                              ans.add(a - b);
                          } else if (c == '+') {
                              ans.add(a + b);
                          } else {
                              ans.add(a * b);
                          }
                      }
                  }
              }
          }
          memo.put(exp, ans);
          return ans;
      }
  }