LeetCode#43 Multiply Strings

Problem Definition:

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

Solution:

1）逐位乘。

 1     # @param {string} num1
 2     # @param {string} num2
 3     # @return {string}
 4     def multiply(self, num1, num2):
 5         if num1=='0' or num2=='0':
 6             return '0'
 7         num1,num2=map(int, num1), map(int, num2)
 8         n1,n2=len(num1), len(num2)
 9         result=[0]*(n1+n2)
10         for i in range(n1-1, -1, -1):
11             carry=0
12             for j in range(n2-1, -1, -1):
13                 pz=(n1-1-i)+(n2-1-j)
14                 result[pz]+=carry+num1[i]*num2[j]
15                 carry=result[pz]/10
16                 result[pz]%=10
17             result[n1-1-i+n2]+=carry
18         19         while result[-1]=='0':
20             result.pop()
21         return ''.join(map(str, result[::-1]))

2）分组乘。64位的二进制数可以表达19位的十进制数，因此两个9位十进制数的乘积可以用64位二进制数存放而不溢出。

因此可以把用数组表示的大整数，每9位为一组，然后group-by-group地相乘，比digit-by-digit会快些。要预处理，对数位分组。

 1     # @param {string} num1
 2     # @param {string} num2
 3     # @return {string}
 4     def multiply(self, num1, num2):
 5         # convert number string into list of 9-digit numbers
 6         def _convert2List(numString):
 7             numList = [0] * ((len(numString) + 8) // 9)
 8             # store 9-digit number in reverse order
 9             numList[0] = int(numString[-9:])
10             for index in range(1, len(numList)):
11                 numList[index] = int(numString[-(index+1)*9 : -index*9])
12             return numList
13 
14         # multiply a number list with a at most 9-digit multiplier
15         def _multiplySingle(result, start, numList, multiplier):
16             carry = 0
17             for index in range(len(numList)):
18                 resultIndex = index + start
19                 carry += (numList[index] * multiplier) + result[resultIndex]
20                 carry, result[resultIndex] = divmod(carry, 1000000000)
21             result[len(numList) + start] = carry
22 
23         if num1 == '0' or num2 == '0':
24             return '0'
25         # convert string to integer
26         num1List, num2List = _convert2List(num1), _convert2List(num2)
27         result = [0] * ((len(num1) + len(num2) + 16) // 9)
28         for index in range(len(num2List)):
29             _multiplySingle(result, index, num1List, num2List[index])
30 
31         # remove leading 0s
32         while result[-1] == 0:
33             result.pop()
34         # convert to string
35         return str(result[-1]) + ''.join(map(lambda x : string.zfill(x, 9), result[:-1][::-1]))

实际上直接写

return str(int(num1)*int(num2))

也能通过，因为Python本身就有处理溢出的机制。int会被自动转换成long，而long是大整数类型，限制其长度的是内存大小。