LeetCode Different Ways to Add Parentheses

LeetCode Different Ways to Add Parentheses

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)) = 2

Output: [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]

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.


给定一个包含+-*的运算字符串,求所有加括号的方案计算到的值。

采用分治法的思路,尝试在每个操作符分成两个部分,这就相当于分别把操作符左右两边括起来单独计算。然后left和right分开进行递归,最后merge。递归的终止条件是当字符串中不包含操作符时,直接返回这个字符串对应的数值。

分治法很经典的例子。

代码如下:

class Solution {
private:
	int operate(int a, int b, char c) {
		switch (c) {
			case '+':return a + b;
			case '-':return a - b;
			case '*':return a*b;
		}
	}
public:
	vector<int> diffWaysToCompute(string input) {
		int n = input.size();
		vector<int> ans;
		bool found = false;
		for (int i = 0; i < n; ++i) {
			if (input[i] == '+' || input[i] == '-' || input[i] == '*') {
				found = true;
				vector<int> lefts = diffWaysToCompute(input.substr(0, i));
				vector<int> rights = diffWaysToCompute(input.substr(i + 1));
				for (int j = 0; j < lefts.size(); ++j) {
					for (int k = 0; k < rights.size(); ++k) {
						ans.push_back(operate(lefts[j], rights[k], input[i]));
					}
				}
			}
		}
		if (!found)return{ atoi(input.c_str()) };
		return ans;
	}
};

本代码提交AC,用时3MS。

Leave a Reply

Your email address will not be published. Required fields are marked *