Python solution use dp


  • 5
    Y

    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]

  • 0
    H

    Any explanation?? I am lost in last for loops


  • 0
    Y

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


  • 0
    H

    Thanks for your explanation. Great work!


Log in to reply
 

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