Different Ways to Add Parentheses

2019-11-06 07:07:04

字体：大中小

来源：转载

供稿：网友

题目

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"

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

Example 2 Input:

"2*3-4*5"(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

Output:[-34, -14, -10, -10, 10]

分析

显然，根据类型限定，我们要使用分治的方法来解决。如例子所述，2*3-4*5 含有三个运算符，可以表示为

(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

共5种方式；可以将其分为2与3-4*5的每个结果向乘还有2*3-4的每个结果与5向乘，还有((2*(3-4))*5) 也就是说，可以用递归将其变为计算两个数的“-” “+” “*”最后再将每种分发的结果显示出来；

当只有两个数时，很容易写出代码：

if (cur == '+')result.push_back(n1 + n2);else if (cur == '-')result.push_back(n1 - n2);elseresult.push_back(n1 * n2);

在这之前，每次遇到运算符时，用substr()将其分为前后两个部分递归

vector<int> result1 = diffWaysToCompute(input.substr(0, i));vector<int> result2 = diffWaysToCompute(input.substr(i+1));

最后可以写出所有代码了

class Solution {public: vector<int> diffWaysToCompute(string input) { vector<int> result; int size = input.size(); for (int i = 0; i < size; i++) { char cur = input[i]; if (cur == '+' || cur == '-' || cur == '*') { vector<int> result1 = diffWaysToCompute(input.substr(0, i)); vector<int> result2 = diffWaysToCompute(input.substr(i+1)); for (auto n1 : result1) { for (auto n2 : result2) { if (cur == '+') result.push_back(n1 + n2); else if (cur == '-') result.push_back(n1 - n2); else result.push_back(n1 * n2); } } } } return result; }};

但是… 尽然是错的？？？ excuse me？原来，尽然有字符串只为一个数字的情况。。。所以正确代码如下：

上一篇：Leetcode-38. Count and Say

下一篇：VS + wxWidgets开发配置指南