43. Multiply Strings

43. Multiply Strings

1 题目

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"

Note:

1. The length of both num1 and num2 is < 110.
2. Both num1 and num2 contain only digits 0-9.
3. Both num1 and num2 do not contain any leading zero, except the number 0 itself.
4. You must not use any built-in BigInteger library or convert the inputs to integerdirectly.

2 解题 && 思路

不难做，模拟乘法。注意边界条件

3. 实现

class Solution(object):
    def multiply(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        r = [ [ ] for i in range(len(num2)) ]
        max_l = 0
        for i in range(len(num2)-1,-1,-1):
            carry_bit = 0
            for t in range(0,len(num2)-1-i):
                r[i].append(0)
   
            for j in range(len(num1)-1,-1,-1):
                tmp = int(num1[j]) * int(num2[i]) + carry_bit 
                if tmp >=10 :
                    carry_bit = tmp / 10
                    tmp = tmp % 10
                else:
                    carry_bit = 0
                r[i].append(tmp)

            if carry_bit != 0:
                r[i].append(carry_bit)
            if len(r[i]) > max_l:
                max_l = len(r[i])
        i =  0 
        ret =""
        print r
        carry_bit = 0
        is_no_zore=False
        while i<max_l:
            tmp = 0

            for e in r :
                if i>=len(e):
                    continue
                tmp = e[i] + tmp 
            tmp = tmp + carry_bit
            if tmp >= 10 :
                carry_bit = tmp / 10
                tmp = tmp % 10
            else:
                carry_bit=0
            if tmp != 0 :
                is_no_zore = True
            ret = str(tmp)+ret
            i = i + 1 
        if carry_bit != 0:
            ret = str(carry_bit)+ret
        return  ret if is_no_zore == True else "0"