leetcode [Divide and Conquer] No.241 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 *.

Example1:

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

Example2:

Input: “23-45”
Output: [-34, -14, -10, -10, 10]
Explanation:
(2*(3-(45))) = -34
((23)-(45)) = -14
((2(3-4))5) = -10
(2((3-4)5)) = -10
(((23)-4)*5) = 10

解题思路

对于Example2中的计算式(2*(3-(4*5))) = -34，我们可以画出如下树状图：

通过树状图我们可以清晰的看到该式的计算过程，首先是乘法，结果为左子树的结果乘上右子树的结果，然后是减法，同样，结果为左子树的结果减去右子树的结果。从中得到启发，我们发现该问题可以用分治的思想来解决。一个算式加上括号后有多少种计算结果，可以看做将这个算式构造成上图形式的树，有多少种构造方法。我们假定一个算式中，有一个计算的符号为$\oplus$⊕，则以$\oplus$⊕为分界，将这个算式分成两部分，这时，一个大问题便可以分成两个小问题：整个算式以$\oplus$⊕为第一个计算符号的所有计算结果，等于左边部分所有的计算结果 $\oplus$⊕ 右边部分所有计算结果，即以$\oplus$⊕为树的根，左边部分以相同的方法构建左子树，右边部分构建右子树。那么一个算式所有的计算结果便是依次以式中所有的符号为根，构建左子树和右子树，最后将所有的结果合在一起，便是答案。

代码：

class Solution {
public:
    vector<int> diffWaysToCompute(string input) {
        vector<int> ret;
        for(int i = 0; i < input.length(); i++) {
        	if (input[i] == '+' || input[i] == '-' || input[i] == '*') {
        		//计算左子树中的结果
        		vector<int> left(diffWaysToCompute(input.substr(0, i)));
        		//计算右子树中的结果
        		vector<int> right(diffWaysToCompute(input.substr(i+1, input.length())));
        		//合并左右子树的结果
        		for (auto itl : left) {
        			for (auto itr : right) {
        				switch(input[i]) {
        					case '+':
        						ret.push_back(itl + itr);
        						break;
        					case '-':
        						ret.push_back(itl - itr);
        						break;
        					case '*':
        						ret.push_back(itl * itr);
        						break;
						}
					}
				}
			}
		}
		//无运算符，则结果为式子中唯一的数字
		if (ret.empty()) {
			ret.push_back(parseInt(input));
		} 
		//对结果进行排序
		sort(ret.begin(), ret.end());
		return ret;
    }
    
private:
	//将字符串转化成数字
	int parseInt(string str) {
		int ret = 0;
		for (auto iter : str) {
			ret = ret * 10 + iter - '0';
		}
		return ret;
	}
};

运行结果：

在该问题中，运用分治的思想并不是为了提高算法的效率，而是使得编程更加清晰简洁的解决这个问题，因为直接运用枚举的话，我们很难不重复的枚举所有可能的结果。虽然结果显示代码的效率不是很高，但实际上整个程序也只运行了16ms，至于效率上的损失，是因为字符串处理没有做到最好，还有就是多次对结果进行排序也浪费了很多时间，但整体思路是对的，稍加优化便可以运行的更快。