241.为运算表达式设计优先级

链接：241.为运算表达式设计优先级
难度：Medium
标签：递归、记忆化搜索、数学、字符串、动态规划
简介：给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, -  以及  * 。

题解 1 - typescript

• 编辑时间：2021-10-25
• 执行用时：88ms
• 内存消耗：41.3MB
• 编程语言：typescript
• 解法介绍：对于每个操作符当作根节点计算。

function diffWaysToCompute(expression: string): number[] {
  return dfs(expression);
  function split(expression: string, idx: number) {
    return [expression.substring(0, idx), expression.substring(idx + 1)];
  }
  function comp(num1: number, num2: number, op: string): number {
    switch (op) {
      case '+':
        return num1 + num2;
      case '-':
        return num1 - num2;
      case '*':
        return num1 * num2;
      default:
        return num1 + num2;
    }
  }
  function dfs(expression: string): number[] {
    const n = expression.length;
    const opIdxs: number[] = [];
    for (let i = 0; i < n; i++) {
      const ch = expression[i];
      if (ch === '+' || ch === '-' || ch === '*') opIdxs.push(i);
    }
    if (opIdxs.length === 0) return [+expression];
    const ans: number[] = [];
    for (const idx of opIdxs) {
      const [left, right] = split(expression, idx);
      for (const num1 of dfs(left)) {
        for (const num2 of dfs(right)) {
          ans.push(comp(num1, num2, expression[idx]));
        }
      }
    }
    return ans;
  }
}

题解 2 - cpp

• 编辑时间：2022-07-01
• 执行用时：8ms
• 内存消耗：12.4MB
• 编程语言：cpp
• 解法介绍：分治。

class Solution {
   public:
    unordered_set<char> opset;
    Solution() {
        opset.insert('+');
        opset.insert('-');
        opset.insert('*');
    }
    vector<int> diffWaysToCompute(string expression) {
        vector<int> ans, oplist;
        int n = expression.size();
        for (int i = 0; i < n; i++) {
            if (opset.count(expression[i])) oplist.push_back(i);
        }
        if (oplist.size() == 0)
            ans.push_back(toNum(expression));
        else
            dfs(expression, oplist, ans);
        return ans;
    }
    int toNum(string &expression) {
        int num = 0, n = expression.size(), i = 0;
        while (i < n && !opset.count(expression[i]))
            num = num * 10 + expression[i++] - '0';
        return num;
    }
    void dfs(string &expression, vector<int> &oplist, vector<int> &ans) {
        for (auto &idx : oplist) {
            vector<int> llist = diffWaysToCompute(expression.substr(0, idx));
            vector<int> rlist = diffWaysToCompute(
                expression.substr(idx + 1, expression.size() - idx));
            for (auto &num1 : llist) {
                for (auto &num2 : rlist) {
                    switch (expression[idx]) {
                        case '+':
                            ans.push_back(num1 + num2);
                            break;
                        case '-':
                            ans.push_back(num1 - num2);
                            break;
                        case '*':
                            ans.push_back(num1 * num2);
                            break;
                    }
                }
            }
        }
    }
};

题解 3 - cpp

• 编辑时间：2022-07-01
• 执行用时：8ms
• 内存消耗：12.4MB
• 编程语言：cpp
• 解法介绍：分治。

class Solution {
   public:
    unordered_set<char> opset;
    Solution() {
        opset.insert('+');
        opset.insert('-');
        opset.insert('*');
    }
    vector<int> diffWaysToCompute(string expression) {
        vector<int> ans, oplist;
        int n = expression.size();
        for (int i = 0; i < n; i++) {
            if (opset.count(expression[i])) oplist.push_back(i);
        }
        if (oplist.size() == 0)
            ans.push_back(toNum(expression));
        else
            dfs(expression, oplist, ans);
        return ans;
    }
    int toNum(string &expression) {
        int num = 0, n = expression.size(), i = 0;
        while (i < n && !opset.count(expression[i]))
            num = num * 10 + expression[i++] - '0';
        return num;
    }
    void dfs(string &expression, vector<int> &oplist, vector<int> &ans) {
        for (auto &idx : oplist) {
            vector<int> llist = diffWaysToCompute(expression.substr(0, idx));
            vector<int> rlist = diffWaysToCompute(
                expression.substr(idx + 1, expression.size() - idx));
            for (auto &num1 : llist) {
                for (auto &num2 : rlist) {
                    switch (expression[idx]) {
                        case '+':
                            ans.push_back(num1 + num2);
                            break;
                        case '-':
                            ans.push_back(num1 - num2);
                            break;
                        case '*':
                            ans.push_back(num1 * num2);
                            break;
                    }
                }
            }
        }
    }
};