Leetcode 241. Different Ways to Add Parentheses (python+cpp)

题目

解法：divide and conquer

这道题目用的是分治法，分治法是递归的把问题拆分为子问题，然后对子问题分别求解。我们熟悉的动态规划就是分治法的一种。

对于这道题目，关键在于这个加括号的操作如何进行转化。对于加括号来说，无非就是改变式子某些部分的运算优先级，换言之就是哪个子问题先算，哪个子问题后算的问题。通过观察我们可以发现，加括号的操作可以变成对于某个运算符号两边的左右子问题分别计算的操作。比如对于上面第二个例子，“2x3-4x5"对应的第二种可能性((2x3)-(4x5)) = -14 ，对应的就是首先计算”-"两边的左右子问题，然后对于左右子问题有分别计算求解的顺序。对于最后的答案就是左右两边子问题的所有可能性进行组合。总结来说就是把加括号的操作变成() ? ()的表达，对于?选取所有可能位置的运算符号，而对于()内的内容，递归的进行拆分，知道左右两边只包含数字可以直接进行计算。

有两个需要注意的地方：

• 对于边界情况的处理，当某一边只有数字而没有运算符的情况的时候，说明这个字问题无需任何操作，直接以这个数字作为结果进行返回即可
• 观察到给出的例子里有重复的结果，所以对于所有结果，我们无需任何判断，直接把所有遍历的结果放入列表即可

python代码如下：

class Solution:def diffWaysToCompute(self, input: str) -> List[int]:	if input.isdigit():return [int(input)]res = []for i in range(len(input)):if input[i] in '+-*':lefts = self.diffWaysToCompute(input[:i])rights = self.diffWaysToCompute(input[i+1:])for left in lefts:for right in rights:if input[i] == '+':res.append(left+right)elif input[i] == '-':res.append(left-right)else:res.append(left*right)return res

C++版本如下：
在python里我们可以很直接的用isdigit来判断当前input是否只包含数字，但是C++中做类似的判断好像比较麻烦。所以C++的写法，把对这个边界情况的判断放到最后，如果说当前input只包含数字的话，那么前面的关于运算符的操作都不会被执行，所以res会是空列表，以这个作为标准进行判断。

class Solution {
    
public:vector<int> diffWaysToCompute(string input) {
    vector<int> res;for (int i=0;i<input.size();i++){
    if (input[i]=='+' or input[i]=='-' or input[i]=='*'){
    vector<int> lefts = diffWaysToCompute(input.substr(0,i));vector<int> rights = diffWaysToCompute(input.substr(i+1));for (auto left:lefts){
    for (auto right:rights){
    if (input[i] == '+'){
    res.push_back(left+right);}else if(input[i] == '-'){
    res.push_back(left-right);}else res.push_back(left*right);}}}}if (res.empty()) res.push_back(stoi(input));return res;}
};

参考链接：
https://blog.csdn.net/fuxuemingzhu/article/details/79568487
https://www.cnblogs.com/grandyang/p/4682458.html
http://bookshadow.com/weblog/2015/07/27/leetcode-different-ways-add-parentheses/