241. Different Ways to Add Parentheses

  • 42.2%

https://leetcode.com/problems/different-ways-to-add-parentheses/#/description

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 *.

1
2
3
4
5
6
Example 1
Input: "2-1-1".

((2-1)-1) = 0
(2-(1-1)) = 2
Output: [0, 2]
1
2
3
4
5
6
7
8
9
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]

https://discuss.leetcode.com/topic/19906/c-4ms-recursive-dp-solution-with-brief-explanation

方法一:

C++ 4ms Recursive & DP solution with brief explanation

Here is the basic recursive solution

一个是分治法

学习一下atoi(input.c_str()), atoi函数Convert string to integer

substr(0, i) 0表示开始位置的index,i表示开index开始后的个数。

substr(i+1),表示从i+1开始至字符串结尾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
vector<int> diffWaysToCompute(string input) {
vector<int> result;
int size = input.size();
for (int i = 0; i < size; i++) {
char cur = input[i];
if (cur == '+' || cur == '-' || cur == '*') {
// Split input string into two parts and solve them recursively
vector<int> result1 = diffWaysToCompute(input.substr(0, i));
vector<int> result2 = diffWaysToCompute(input.substr(i+1));
for (auto n1 : result1) {
for (auto n2 : result2) {
if (cur == '+')
result.push_back(n1 + n2);
else if (cur == '-')
result.push_back(n1 - n2);
else
result.push_back(n1 * n2);
}
}
}
}
// if the input string contains only number,这种情况要考虑到
if (result.empty())
result.push_back(atoi(input.c_str()));
return result;
}
};

方法二:

类似于分治法,但是用到了dp,保存部分结果到一个map里,方便查询,节约了计算。

There are many repeating subquestions in this recursive method, therefore, we could use dynamic programming to avoid this situation by saving the results for subquestions. Here is the DP solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
vector<int> diffWaysToCompute(string input) {
unordered_map<string, vector<int>> dpMap; // 注意此处map的定义,key为string,value为vector<int>
return computeWithDP(input, dpMap);
}

vector<int> computeWithDP(string input, unordered_map<string, vector<int>> &dpMap) {
vector<int> result;
int size = input.size();
for (int i = 0; i < size; i++) {
char cur = input[i];
if (cur == '+' || cur == '-' || cur == '*') {
// Split input string into two parts and solve them recursively
vector<int> result1, result2;
string substr = input.substr(0, i);
// check if dpMap has the result for substr
if (dpMap.find(substr) != dpMap.end())
result1 = dpMap[substr];
else
result1 = computeWithDP(substr, dpMap);

substr = input.substr(i + 1);
if (dpMap.find(substr) != dpMap.end()) // 学习字典的查找写法
result2 = dpMap[substr];
else
result2 = computeWithDP(substr, dpMap);

for (auto n1 : result1) {
for (auto n2 : result2) {
if (cur == '+')
result.push_back(n1 + n2);
else if (cur == '-')
result.push_back(n1 - n2);
else
result.push_back(n1 * n2);
}
}
}
}
// if the input string contains only number
if (result.empty())
result.push_back(atoi(input.c_str())); // 这一步值得学习
// save to dpMap
dpMap[input] = result; // 不要忘记这一步
return result;
}
};

https://discuss.leetcode.com/topic/19894/1-11-lines-python-9-lines-c

1-11 lines Python, 9 lines C++

Just doing it…

Solution 1 … 48 ms

1
2
3
4
5
6
7
8
9
10
11
12
def diffWaysToCompute(self, input):
tokens = re.split('(\D)', input)
nums = map(int, tokens[::2])
ops = map({'+': operator.add, '-': operator.sub, '*': operator.mul}.get, tokens[1::2])
def build(lo, hi):
if lo == hi:
return [nums[lo]]
return [ops[i](a, b)
for i in xrange(lo, hi)
for a in build(lo, i)
for b in build(i + 1, hi)]
return build(0, len(nums) - 1)

Solution 2 … 168 ms

One-liner inspired by Soba.

1
2
3
4
5
def diffWaysToCompute(self, input):
return [eval(`a`+c+`b`)
for i, c in enumerate(input) if c in '+-*'
for a in self.diffWaysToCompute(input[:i])
for b in self.diffWaysToCompute(input[i+1:])] or [int(input)]

Solution 3 … 64 ms

Faster version of solution 2.

1
2
3
4
5
def diffWaysToCompute(self, input):
return [a+b if c == '+' else a-b if c == '-' else a*b
for i, c in enumerate(input) if c in '+-*'
for a in self.diffWaysToCompute(input[:i])
for b in self.diffWaysToCompute(input[i+1:])] or [int(input)]

Solution 4 … 188 ms

A code golf version of solution 2.

1
2
diffWaysToCompute=d=lambda s,t:[eval(`a`+c+`b`)for i,c in enumerate(t)if
c<'0'for a in s.d(t[:i])for b in s.d(t[i+1:])]or[int(t)]

C++ … 8 ms

C++ version of solution 3.

1
2
3
4
5
6
7
8
9
10
11
vector<int> diffWaysToCompute(string input) {
vector<int> output;
for (int i=0; i<input.size(); i++) {
char c = input[i];
if (ispunct(c))
for (int a : diffWaysToCompute(input.substr(0, i)))
for (int b : diffWaysToCompute(input.substr(i+1)))
output.push_back(c=='+' ? a+b : c=='-' ? a-b : a*b);
}
return output.size() ? output : vector<int>{stoi(input)};
}

https://discuss.leetcode.com/topic/22179/python-easy-to-understand-solution-divide-and-conquer

Python easy to understand solution (divide and conquer).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def diffWaysToCompute(self, input):
if input.isdigit():
return [int(input)]
res = []
for i in xrange(len(input)):
if input[i] in "-+*":
res1 = self.diffWaysToCompute(input[:i])
res2 = self.diffWaysToCompute(input[i+1:])
for j in res1:
for k in res2:
res.append(self.helper(j, k, input[i]))
return res

def helper(self, m, n, op):
if op == "+":
return m+n
elif op == "-":
return m-n
else:
return m*n

https://discuss.leetcode.com/topic/27532/14-line-c-solution

14-line c++ solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:

vector<int> diffWaysToCompute(string input) {
vector<int> ans;
bool pureNum=true;
for (int i=0; i<input.length(); i++)
if (input[i]<'0' || input[i]>'9') {
pureNum=false;
vector<int> L=diffWaysToCompute(input.substr(0, i)), R=diffWaysToCompute(input.substr(i+1, input.length()-i-1));
for (auto l : L)
for (auto r : R)
if (input[i]=='+') ans.push_back(l+r);
else if (input[i]=='-') ans.push_back(l-r);
else if (input[i]=='*') ans.push_back(l*r);
}

if (pureNum)
ans.push_back(atoi(input.c_str()));
return ans;
}
};

https://discuss.leetcode.com/topic/20516/c-solution-using-dp-easy-understanding

C++ solution, using dp, easy understanding

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
vector<int> diffWaysToCompute(string input) {
vector<int> data;
vector<char> ops;
int num = 0;
char op = ' ';
istringstream ss(input + "+");
while(ss >> num && ss >> op) {
data.push_back(num);
ops.push_back(op);
}
const int size_i = data.size();
vector<vector<vector<int>>> dp(size_i, vector<vector<int>>(size_i, vector<int>()));
for (int i = 0; i < size_i; i += 1)
for (int j = i; j >= 0; j -= 1) {
if (i == j) {dp[j][i].push_back(data[i]); continue;}
for (int k = j; k < i; k += 1) {
for (auto left : dp[j][k])
for (auto right : dp[k+1][i]) {
int val = 0;
switch(ops[k]) {
case '+': val = left + right; break;
case '-': val = left - right; break;
case '*': val = left * right; break;
}
dp[j][i].push_back(val);
}
}
}
return dp[0][size_i-1];
}

https://discuss.leetcode.com/topic/20814/python-solution-use-dp

Python solution use dp

First I extracted the numbers and operators in the expression. Assume there are d numbers and d-1 operators.

dp[ i ][ j ] is all possible results of expression contains num[ i : j+1 ].

So the first loop we calculate expressions only have 2 numbers, then 3 numbers, then 4 numbers….

Let’s say we want to get the result of expression contains L numbers started from num[ j ] , we divide it by two half, the first one contains k numbers, and the second half contains L-k numbers. The result of the first half is dp[ j ][ j+k-1 ] and the second half is dp[j+k-1][ j+l-1]. dp[ i ][ j ] contains all combinations of x from dp[ j ][ j+k-1 ] and y from dp[ j+k-1: j+l-1 ], and k is from 1 to l-1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import re
class Solution:
# @param {string} input
# @return {integer[]}
def diffWaysToCompute(self, input):
num=re.split('\+|-|\*',input)
opr=re.findall(r'\+|-|\*',input)
d=len(num)
dp=[[[]for i in range(d)] for j in range(d)]
op={'+':lambda x,y:x+y, '-':lambda x,y:x-y, '*':lambda x,y:x*y}
for i in range(d):
dp[i][i].append(int(num[i]))
for l in range(2,d+1):
for j in range(d+1-l):
dp[j][j+l-1]=[op[opr[j+k-1]](x,y)
for k in range(1,l) for x in dp[j][j+k-1] for y in dp[j+k][j+l-1]]
return dp[0][d-1]

10ms, 15.08%, October 15, 2016

https://discuss.leetcode.com/topic/19901/a-recursive-java-solution-284-ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Solution {
public List<Integer> diffWaysToCompute(String input) {
List<Integer> ret = new LinkedList<Integer>();
for(int i=0; i<input.length(); i++){
if(input.charAt(i) == '-' ||
input.charAt(i) == '*' ||
input.charAt(i) == '+'){
String part1 = input.substring(0, i);
String part2 = input.substring(i+1);
List<Integer> part1Ret = diffWaysToCompute(part1);
List<Integer> part2Ret = diffWaysToCompute(part2);
for(Integer p1 : part1Ret){
for(Integer p2:part2Ret){
int c = 0;
switch(input.charAt(i)){
case '+': c = p1+p2;
break;
case '-':c = p1-p2;
break;
case '*': c = p1*p2;
break;
}
ret.add(c);
}
}
}
}
if(ret.size() == 0)
ret.add(Integer.valueOf(input));
return ret;
}
}
谢谢你,可爱的朋友。