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
Example 1+, - and *.
Input:
"2-1-1".((2-1)-1) = 0 (2-(1-1)) = 2
Output:
Example 2[0, 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]
[Thoughts]
这题就是分治法- Divide and Conquer的一个例子。在递归的过程中，根据符号位，不断将一个字符串分成两个子串，然后将两个子串的结果merge起来。
[Code]
1: class Solution {
2: public:
3: int compute(int a, int b, char op) {
4: switch(op) {
5: case '+': return a + b;
6: case '-': return a - b;
7: case '*': return a * b;
8: }
9: }
10: vector<int> diffWaysToCompute(string input) {
11: int number = 0, i=0;
12: for(; i< input.length() && isdigit(input[i]); ++i) {
13: number = number * 10 + input[i]-'0';
14: }
15: // if pure number, just return
16: if(i == input.length()) return {number};
17: vector<int> diffWays, lefts, rights;
18: for(int i =0; i< input.length(); i++) {
19: if(isdigit(input[i])) continue;
20: lefts =
21: diffWaysToCompute(input.substr(0, i));
22: rights =
23: diffWaysToCompute(input.substr(i + 1, input.length() - i - 1));
24: for(int j = 0; j < lefts.size(); ++j)
25: for( int k =0; k < rights.size(); ++k)
26: diffWays.push_back(compute(lefts[j], rights[k], input[i]));
27: }
28: return diffWays;
29: }
30: };
Github: https://github.com/codingtmd/leetcode/blob/master/src/Different%20Ways%20to%20Add%20Parentheses.cpp
Note: 已有的实现有大量的重复计算，如果想进一步优化时间的话，可以考虑用memoization来避免冗余计算。比如，用个hash map 来保存中间计算的结果，如下：
github: https://github.com/codingtmd/leetcode/blob/master/src/Different%20Ways%20to%20Add%20Parentheses(Memoization).cpp
1: class Solution {
2: public:
3: unordered_map<string, vector<int>> memo;
4: int compute(int a, int b, char op) {
5: switch(op) {
6: case '+': return a + b;
7: case '-': return a - b;
8: case '*': return a * b;
9: }
10: }
11: string generateKey(int startIndex, int endIndex) {
12: return to_string(startIndex) + "-" + to_string(endIndex);
13: }
14: vector<int> diffWaysToCompute(string input) {
15: return diffWaysToComputeWithMemo(input, 0, input.size()-1);
16: }
17: vector<int> diffWaysToComputeWithMemo(string& input, int startIndex, int endIndex) {
18: string cache_key = generateKey(startIndex, endIndex);
19: if(memo.find(cache_key) != memo.end()) return memo[cache_key];
20: int number = 0, i=startIndex;
21: for(; i<= endIndex && isdigit(input[i]); ++i) {
22: number = number * 10 + input[i]-'0';
23: }
24: // if pure number, just return
25: if(i > endIndex) return {number};
26: vector<int> diffWays, lefts, rights;
27: for(int i =startIndex; i< endIndex; i++) {
28: if(isdigit(input[i])) continue;
29: lefts =
30: diffWaysToComputeWithMemo(input, startIndex, i-1);
31: rights =
32: diffWaysToComputeWithMemo(input, i+1, endIndex );
33: for(int j = 0; j < lefts.size(); ++j)
34: for( int k =0; k < rights.size(); ++k)
35: diffWays.push_back(compute(lefts[j], rights[k], input[i]));
36: }
37: memo[cache_key] = diffWays;
38: return diffWays;
39: }
40: };
github: https://github.com/codingtmd/leetcode/blob/master/src/Different%20Ways%20to%20Add%20Parentheses(Memoization).cpp
