[Leetcode][Python]43: Multiply Strings

# -*- coding: utf8 -*-
‘‘‘
__author__ = ‘[email protected]

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[i]) * int(num2[j]) + 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[i]) + int(num2[i]) + 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)

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。