Thursday, September 18, 2014

Leetcode: Multiply Strings @Python

class Solution:
    # @param num1, a string
    # @param num2, a string
    # @return a string
    def multiply(self, num1, num2):
        n=len(num1)
        m=len(num2)
        num1=[int(i) for i in reversed(num1)]
        num2=[int(i) for i in reversed(num2)]
        if n*m==0:
            return None
        elif num1==[0] or num2==[0]:
            return '0'
        rst=[0]*(m+n)
        for i in range(n):
            for j in range(m):
                a2,a1=divmod(num1[i]*num2[j],10) #c1,c2<=1
                c1,rst[i+j]=divmod(a1+rst[i+j],10)
                c2,rst[i+j+1]=divmod(a2+c1+rst[i+j+1],10)
                k=2
                while c2:
                    c2,rst[i+j+k]=divmod(c2+rst[i+j+k],10)
                    k+=1
        if rst[n+m-1]:
            return ''.join(map(str,reversed(rst)))
        else:
            return ''.join(map(str,reversed(rst[:n+m-1])))                    

No comments :

Post a Comment