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

``````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]``````

• Any explanation?? I am lost in last for loops

• I added explanation to it just now.
Inside the loops there is a list comprehension, you could translate it into:
for k in range(1,l):
for x in dp[j][j+k-1]:
for y in dp[j+k][j+l-1]]:
dp[j][j+l-1].append(op opr[j+k-1] )

• Thanks for your explanation. Great work!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.