241. Different Ways to Add Parentheses

问题：

给定一个字符串，表示一个由+-*三种运算符组成的算式。

求给运算式任意加括号，使得计算优先顺序变化。

所得所有结果的可能。

Example 1:
Input: expression = "2-1-1"
Output: [0,2]
Explanation:
((2-1)-1) = 0 
(2-(1-1)) = 2

Example 2:
Input: expression = "2*3-4*5"
Output: [-34,-14,-10,-10,10]
Explanation:
(2*(3-(4*5))) = -34 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(2*((3-4)*5)) = -10 
(((2*3)-4)*5) = 10
 

Constraints:
1 <= expression.length <= 20
expression consists of digits and the operator '+', '-', and '*'.

　　

解法：recursion（递归）divide and conquer（分治）

将大问题划分为子问题，再合并求解子问题得到的结果。

本问题，加括号，存在嵌套，

即可看作：典型递归。每层嵌套即为一层递归。

• 分治方法：
• 切分子问题：对一个算式加括号：在任意运算号处，划分为：左右两个子问题。

• • （这里，为什么不是3个or4个甚至更多子问题？
  • 运算本质来看，都是两部分进行求解。化成更多问题，其实也就==相当于两个问题内部再嵌套子问题）

• 合并子问题的解：
  • 对左右两边得到的结果list，
  • 两两进行中间符号运算，加入res中。

• base：递归出口（最终子问题）
  • 传入运算式==数字，不包含运算符。
  • 那么就直接，将数字化为int型变量，返回。

代码参考：

class Solution {
public:
    unordered_map<string, vector<int>> memo;
    //recursion
    //Divide and conquer
    vector<int> diffWaysToCompute(string expression) {
        if(memo.count(expression)!=0) return memo[expression];
        vector<int> res;
        for(int i=0; i<expression.length(); i++) {
            char c=expression[i];
            if(c=='+' || c=='-' ||c=='*') {//divide
                string left = expression.substr(0, i);
                string right = expression.substr(i+1);
                vector<int> lres = diffWaysToCompute(left);
                vector<int> rres = diffWaysToCompute(right);
                //conquer
                for(int l:lres) {
                    for(int r:rres) {
                        switch(c) {
                            case '+': res.push_back(l+r);break;
                            case '-': res.push_back(l-r);break;
                            case '*': res.push_back(l*r);break;
                            default: break;
                        }
                    }
                }
            }
        }
        //base
        if(res.empty()) res.push_back(atoi(expression.c_str()));
        return res;
    }
};