Python easy to understand solution (divide and conquer).


  • 39
    C
    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

  • 0
    Z

    Elegant solution. Is this really divide and conquer? It is more like a different ordering of the signs.


  • 0
    O

    They are divide and conquer:

    res1 = self.diffWaysToCompute(input[:i])

    res2 = self.diffWaysToCompute(input[i+1:])


  • 3
    C

    An even shorter version:

     def diffWaysToCompute(self, input):
        if input.isdigit():
            return [eval(input)]
        res = []
        for i, s in enumerate(input):
            if s in "+-*":
                l = self.diffWaysToCompute(input[:i])
                r = self.diffWaysToCompute(input[i+1:])
                res.extend(self.compute(l, r, s))
        return res 
                
    def compute(self, l, r, op):
        return [eval(str(m)+op+str(n)) for m in l for n in r]

  • 6
    C

    why not shorter?

    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:])
                res += [eval(str(k)+input[i]+str(j)) for k in res1 for j in res2]            
        return res

  • 0
    C

    Yes, this is a good one.


  • 0
    X

    It's shorter but cost more time.


Log in to reply
 

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