Recursion
Memoization
Math
String
Dynamic Programming
Description
Given a string expression
of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators . You may return the answer in any order .
The test cases are generated such that the output values fit in a 32-bit integer and the number of different results does not exceed 104
.
Example 1:
Input: expression = "2-1-1"
Output: [0,2]
Explanation:
((2-1)-1) = 0
(2-(1-1)) = 2
Example 2:
Input: expression = "2*3-4*5"
Output: [-34,-14,-10,-10,10]
Explanation:
(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
Constraints:
1 <= expression.length <= 20
expression
consists of digits and the operator '+'
, '-'
, and '*'
.
All the integer values in the input expression are in the range [0, 99]
.
The integer values in the input expression do not have a leading '-'
or '+'
denoting the sign.
Solutions
Solution 1
Python3 Java C++ Go C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 class Solution :
def diffWaysToCompute ( self , expression : str ) -> List [ int ]:
@cache
def dfs ( exp ):
if exp . isdigit ():
return [ int ( exp )]
ans = []
for i , c in enumerate ( exp ):
if c in '-+*' :
left , right = dfs ( exp [: i ]), dfs ( exp [ i + 1 :])
for a in left :
for b in right :
if c == '-' :
ans . append ( a - b )
elif c == '+' :
ans . append ( a + b )
else :
ans . append ( a * b )
return ans
return dfs ( expression )
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 class Solution {
private static Map < String , List < Integer >> memo = new HashMap <> ();
public List < Integer > diffWaysToCompute ( String expression ) {
return dfs ( expression );
}
private List < Integer > dfs ( String exp ) {
if ( memo . containsKey ( exp )) {
return memo . get ( exp );
}
List < Integer > ans = new ArrayList <> ();
if ( exp . length () < 3 ) {
ans . add ( Integer . parseInt ( exp ));
return ans ;
}
for ( int i = 0 ; i < exp . length (); ++ i ) {
char c = exp . charAt ( i );
if ( c == '-' || c == '+' || c == '*' ) {
List < Integer > left = dfs ( exp . substring ( 0 , i ));
List < Integer > right = dfs ( exp . substring ( i + 1 ));
for ( int a : left ) {
for ( int b : right ) {
if ( c == '-' ) {
ans . add ( a - b );
} else if ( c == '+' ) {
ans . add ( a + b );
} else {
ans . add ( a * b );
}
}
}
}
}
memo . put ( exp , ans );
return ans ;
}
}
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 class Solution {
public :
vector < int > diffWaysToCompute ( string expression ) {
return dfs ( expression );
}
vector < int > dfs ( string exp ) {
if ( memo . count ( exp )) return memo [ exp ];
if ( exp . size () < 3 ) return { stoi ( exp )};
vector < int > ans ;
int n = exp . size ();
for ( int i = 0 ; i < n ; ++ i ) {
char c = exp [ i ];
if ( c == '-' || c == '+' || c == '*' ) {
vector < int > left = dfs ( exp . substr ( 0 , i ));
vector < int > right = dfs ( exp . substr ( i + 1 , n - i - 1 ));
for ( int & a : left ) {
for ( int & b : right ) {
if ( c == '-' )
ans . push_back ( a - b );
else if ( c == '+' )
ans . push_back ( a + b );
else
ans . push_back ( a * b );
}
}
}
}
memo [ exp ] = ans ;
return ans ;
}
private :
unordered_map < string , vector < int >> memo ;
};
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 var memo = map [ string ][] int {}
func diffWaysToCompute ( expression string ) [] int {
return dfs ( expression )
}
func dfs ( exp string ) [] int {
if v , ok := memo [ exp ]; ok {
return v
}
if len ( exp ) < 3 {
v , _ := strconv . Atoi ( exp )
return [] int { v }
}
ans := [] int {}
for i , c := range exp {
if c == '-' || c == '+' || c == '*' {
left , right := dfs ( exp [: i ]), dfs ( exp [ i + 1 :])
for _ , a := range left {
for _ , b := range right {
if c == '-' {
ans = append ( ans , a - b )
} else if c == '+' {
ans = append ( ans , a + b )
} else {
ans = append ( ans , a * b )
}
}
}
}
}
memo [ exp ] = ans
return ans
}
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
49
50
51
52
53
54
55
56
57
58
59
60
61 using System.Collections.Generic ;
public class Solution {
public IList < int > DiffWaysToCompute ( string input ) {
var values = new List < int > ();
var operators = new List < char > ();
var sum = 0 ;
foreach ( var ch in input )
{
if ( ch == '+' || ch == '-' || ch == '*' )
{
values . Add ( sum );
operators . Add ( ch );
sum = 0 ;
}
else
{
sum = sum * 10 + ch - '0' ;
}
}
values . Add ( sum );
var f = new List < int > [ values . Count , values . Count ];
for ( var i = 0 ; i < values . Count ; ++ i )
{
f [ i , i ] = new List < int > { values [ i ] };
}
for ( var diff = 1 ; diff < values . Count ; ++ diff )
{
for ( var left = 0 ; left + diff < values . Count ; ++ left )
{
var right = left + diff ;
f [ left , right ] = new List < int > ();
for ( var i = left ; i < right ; ++ i )
{
foreach ( var leftValue in f [ left , i ])
{
foreach ( var rightValue in f [ i + 1 , right ])
{
switch ( operators [ i ])
{
case '+' :
f [ left , right ]. Add ( leftValue + rightValue );
break ;
case '-' :
f [ left , right ]. Add ( leftValue - rightValue );
break ;
case '*' :
f [ left , right ]. Add ( leftValue * rightValue );
break ;
}
}
}
}
}
}
return f [ 0 , values . Count - 1 ];
}
}
GitHub