## Saturday, October 17, 2015

### [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]

[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:  };
``````

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) {
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:  };
``````