Simple accepted recursive solution in python with explanation


  • 0
    L

    the solution is based on the basic multiple rule: abcd=(ac100+ac10+bc10+bd). Here the interval is the maximum number of digit that can directly calculate the multiplication. If the input have more digits than the interval (8), the number would be divided into two part and then recursively calculate the results following that multiplying role.

    class Solution:
        # @param num1, a string
        # @param num2, a string
        # @return a string
    # to add two strings
        def stringPlus(self,num1,num2):
            (ii,res,flag)=(1,'',0)
            (num1,num2)=(num1,num2) if len(num1)>len(num2) else (num2,num1)
            while ii<=len(num2):
                tmp=flag+int(num1[len(num1)-ii])+int(num2[len(num2)-ii])
                if tmp>=10:
                    flag,res=1,str(tmp-10)+res
                else:
                    flag,res=0,str(tmp)+res
                ii+=1
            while flag==1 and ii<=len(num1):
                tmp=flag+int(num1[len(num1)-ii])
                if tmp>=10:
                    flag,res=1,str(tmp-10)+res
                else:
                    flag,res=0,str(tmp)+res
                ii+=1
            if flag==1:
                res='1'+res
            if ii<=len(num1):
                res=num1[0:len(num1)-ii+1]+res
            return res
      # to multiple two strings              
        def multiply(self, num1, num2):
            inteval = 8
            if num1 and num2:
                if len(num1)<=inteval and len(num2)<=inteval:
                    res=str(int(num1)*int(num2))
                elif len(num1)>inteval and len(num2)>inteval:
                    res1=self.multiply(num1[0:int(len(num1)/2)],num2[0:int(len(num2)/2)])
                    if res1!='0':
                        res1+='0'*(int((len(num1)+1)/2)+int((len(num2)+1)/2))
                    res2=self.multiply(num1[int(len(num1)/2):],num2[0:int(len(num2)/2)])
                    if res2!='0':
                        res2+='0'*int((len(num2)+1)/2)
                    res3=self.multiply(num1[0:int(len(num1)/2)],num2[int(len(num2)/2):])
                    if res3!='0':
                        res3+='0'*int((len(num1)+1)/2)
                    res4=self.multiply(num1[int(len(num1)/2):],num2[int(len(num2)/2):])
                    res=self.stringPlus(self.stringPlus(res1,res2),self.stringPlus(res3,res4))
                elif len(num1)>inteval and len(num2)<inteval:
                    res1=self.multiply(num1[0:int(len(num1)/2)],num2)
                    if res1!='0':
                        res1+='0'*int((len(num1)+1)/2)
                    res2=self.multiply(num1[int(len(num1)/2):],num2)
                    res=self.stringPlus(res1,res2)
                else: #len(num1)<inteval and len(num2)>inteval:
                    res1=self.multiply(num1,num2[0:int(len(num2)/2)])
                    if res1!='0':
                        res1+='0'*int((len(num2)+1)/2)
                    res2=self.multiply(num1,num2[int(len(num2)/2):])   
                    res=self.stringPlus(res1,res2)
                return res

Log in to reply
 

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