241.js

/** ------------------------------------------------------------------------------
 * 
 * 241. Different Ways to Add Parentheses
 * Topics: DP Recursion
 * https://leetcode.com/problems/different-ways-to-add-parentheses/description/
 * 
 ------------------------------------------------------------------------------ */
// var diffWaysToCompute = function (expression) {
//   const results = []

//   for (let i = 0; i < expression.length; i++) {
//     if (expression[i] === "+" || expression[i] === "-" || expression[i] === "*" || expression[i] === "/") {
//       const left = diffWaysToCompute(expression.slice(0, i))
//       const right = diffWaysToCompute(expression.slice(i + 1))

//       for (let j = 0; j < left.length; j++) {
//         for (let k = 0; k < right.length; k++) {
//           switch (expression[i]) {
//             case "+":
//               results.push(left[j] + right[k])
//               break
//             case "-":
//               results.push(left[j] - right[k])
//               break
//             case "*":
//               results.push(left[j] * right[k])
//               break
//             case "/":
//               results.push(left[j] / right[k])
//               break
//           }
//         }
//       }
//     }
//   }

//   if (results.length === 0) return [+expression]

//   return results
// }

var diffWaysToCompute = function (expression) {
  const memo = {}

  const ways = (exp) => {
    if (memo[exp]) return memo[exp]

    const result = []

    for (let i = 0; i < exp.length; i++) {
      if (["+", "-", "*", "/"].includes(exp[i])) {
        const left = ways(exp.slice(0, i))
        const right = ways(exp.slice(i + 1))

        for (let j = 0; j < left.length; j++) {
          for (let k = 0; k < right.length; k++) {
            switch (exp[i]) {
              case "+":
                result.push(left[j] + right[k])
                break
              case "-":
                result.push(left[j] - right[k])
                break
              case "*":
                result.push(left[j] * right[k])
                break
              case "/":
                result.push(left[j] / right[k])
                break
              default:
                break
            }
          }
        }
      }
    }

    if (result.length === 0) result.push(+exp)

    memo[exp] = result
    console.log(memo)
    return result
  }

  return ways(expression)
}

console.log(diffWaysToCompute("2*3-4*5"))