Simple Python Solution using Divide and Conquer

  • 2

    Python code is quite simple here.

    Basic idea:

    1. divide the expression into two parts

    2. get the result for the first part and second part

    3. then merge them using another function.
      The python code goes as follows,

      op_dict = {'+':lambda x,y:x+y,'-':lambda x,y:x-y,'':lambda x,y:xy, '/':lambda x,y:x/y}
      class Solution:
      # @param {string} input
      # @return {integer[]}

        # given two list of integers, make a combination result based on op
        def combination(self,list1,list2,op):
            res = []
            for i in list1:
                for j in list2:
                    res += [op_dict[op](i,j)]
            return res
        # split the expression into two parts, each part use a recursive function to achieve
        def rec(self, exp):
            try:# consider the condition if exp is just a integer like '1000'
                return [int(exp)]
                size = len(exp)
                if size == 0:
                     return []
                res = []
                i = 0
                while i < size:
                    if exp[i] >= '0' and exp[i] <= '9':
                        i += 1
                    first = self.rec(exp[:i])
                    second = self.rec(exp[i+1:])
                    op = exp[i]
                    res += self.combination(first,second,op)
                    i += 1
                return res
        def diffWaysToCompute(self, input):
            res = self.rec(input)
            return res

Log in to reply

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