43. Multiply Strings

Multiply Strings

Solution 1:
     The Length is way larger than 64 bit integer, which length is 19
    
     Python3.5: Integers have unlimited precision, in most situations of industrial work, just use the simplest and most readable way to do it.

     Intuitively, multiply digit by digit, and add sum up. Use a String to store temporary result and 'add' it into result.

    Example: 13*34=13*4+13*30
    Here 13 is num1, 14 is num2, need to multiply in reverse order

 def multiply(self, num1, num2):
    if num1 == '0' or num2 == '0':
        return '0'
    revret = '' # store the result in reverse order for easy computation
    zeros='' #this is used for add 0 for next inner iteration
    for d1 in reversed(num1):
        tmp = ''
        offset = 0
        for d2 in reversed(num2):
            sum = int(d2)*int(d1)+offset
            tmp += str(sum%10)
            offset = sum/10
        if offset:
            tmp += str(offset)
        revret = self.addNumInReverse(revret, zeros+tmp)
        zeros+='0'
    return revret[::-1]
def addNumInReverse(num, tmp):

    if len(num) < len(tmp):
        t = tmp
        tmp = num
        num = t

    re = ""
    off = 0
    
    for i, n in enumerate(num):
        sum = off + int(n) + (int(tmp[i]) if i < len(tmp) else 0)
        re+=str(sum%10)
        off = sum/10                     
    if off:
        re += str(off)         
    return re

Solution 2:
Don't have to add it up in when they first multiplied together.   

          
Use array to store each multiplied result, add it up at last.                      

Maximum product length = len(A) + len(B)

def multiply(self, num1, num2):
    if num1 == '0' or num2 == '0':
        return '0'

    retval = [0]*(len(num1)+len(num2))
    num1 = list(reversed(num1))
    num2 = list(reversed(num2))
    k=0

    for i, d1 in enumerate(num1):
        for j, d2 in enumerate(num2):                
            retval[j+k] += int(d1)*int(d2)
        k+=1
    ret = ""
    off = 0

    for i in xrange(len(retval)):
        sum = retval[i] + off
        ret = str(sum%10) + ret
        off = sum/10
    if off:
        ret = off + ret