[Leetcode] Different Ways to Add Parentheses, Solution

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]

[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 来保存中间计算的结果，如下：

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