[Leetcode][Python]43: Multiply Strings
# -*- coding: utf8 -*-'''
__author__ = 'dabay.wang@gmail.com'
43: Multiply Strings
https://leetcode.com/problems/multiply-strings/
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.
=== Comments by Dabay===
用小学学的乘法公式。
'''
class Solution:
# @param num1, a string
# @param num2, a string
# @return a string
def multiply(self, num1, num2):
if num1 == "0" or num2 == "0":
return "0"
# if len(num1) < len(num2):
# num1, num2 = num2, num1
res = ""
for j in reversed(xrange(len(num2))):
tmp = ""
carry = 0
for i in reversed(xrange(len(num1))):
x = int(num1) * int(num2) + carry
carry = x / 10
x = x % 10
tmp = str(x) + tmp
if carry != 0:
tmp = str(carry) + tmp
res = self.num_add(res, tmp + "0" * (len(num2)-1-j))
return res
def num_add(self, num1, num2):
if len(num1) > len(num2):
num2 = num2.zfill(len(num1))
else:
num1 = num1.zfill(len(num2))
res = ""
carry = 0
for i in reversed(xrange(len(num1))):
x = int(num1) + int(num2) + carry
if x >= 10:
x -= 10
carry = 1
else:
carry = 0
res = str(x) + res
if carry == 1:
res = "1" + res
return res
def main():
sol = Solution()
num1 = "999"
num2 = "999"
print sol.num_add(num1, num2)
print sol.multiply(num1, num2)
if __name__ == "__main__":
import time
start = time.clock()
main()
print "%s sec" % (time.clock() - start)
页:
[1]