[leetcode] 241. Different Ways to Add Parentheses

[leetcode] 241. Different Ways to Add Parentheses

Description

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

Example 1:

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

Example 2:

Input: "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

分析

题目的意思是：给你一个表达式，你可以任意加括号，要求返回所有可能计算的结果。

这道题首先会想到递归，把所有的情况都列举出来，我们从运算符分开，分为left，right两个分支，把两个分支的所有的计算结果合并，组合然后就可以满足题目的要求了。

代码

class Solution {public: vector diffWaysToCompute(string input) { vector result; if(input.length()==0){ return result; } for(int i=0;i left=diffWaysToCompute(input.substr(0,i)); vector right=diffWaysToCompute(input.substr(i+1)); for(auto i1:left){ for(auto i2:right){ switch(input[i]){ case '+': result.push_back(i1+i2); break; case '-': result.push_back(i1-i2); break; case '*': result.push_back(i1*i2); break; } } } } } if(result.empty()){ result.push_back(stoi(input)); } return result; }};

参考文献

​​241. Different Ways to Add Parentheses​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。