Leetcode 241. Different Ways to Add Parentheses

2019-11-06 07:47:07

字体：大中小

来源：转载

供稿：网友

source url

Leetcode 53.Maximum Subarray

source url

题目描述

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 *. 输入：一个算式，字符串形式输出：该数组中，不同运算顺序的结果如：

Input:"2-1-1"

((2-1)-1) = 0 (2-(1-1)) = 2

Output:[0, 2]

代码

class Solution {public: vector<int> diffWaysToCompute(string input) { vector<int> results, l, r; int sSize = input.length(); char cur; bool isAllInt = true; for(int i = 0;i<sSize;i++){ cur = input[i]; //if cur char is an operator : '+', '-' or '*' //get different ways computed values of left sub-string and right sub-string //calculate possible results from l`Operate`r if(cur=='-'||cur=='+'||cur=='*'){ isAllInt = false; l = diffWaysToCompute(input.substr(0,i)); r = diffWaysToCompute(input.substr(i+1,sSize)); for(int i =0;i<l.size();i++) for(int j=0;j<r.size();j++) results.push_back(cur=='-'?l[i]-r[j]:cur=='+'?l[i]+r[j]:l[i]*r[j]); } } //return the integer results if(isAllInt){ results.push_back(atoi(input.c_str())); } return results; }};