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.

解题方法

就是用笔算乘法的方法

  • 用一个array先将num1的低i位和num2的第j位存起来，i+j位相乘的积存在 新array的第i+j位
  • 然后再将这个array按照从低位到高位相加，carry处理的方法得到结果

注意点

  • 最后如果前面是0的话要去掉，但是如果只剩“0”的话就要返回

Solution

class Solution(object):
    def multiply(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        if num1 == 0 or num2 == 0:
            return "0"
        length1 = len(num1)
        length2 = len(num2)

        tmp = [0 for i in range(length1 + length2)]
        result = ""

        for i in range(length1):
            d1 = int(num1[length1-1-i])
            for j in range(length2):
                d2 = int(num2[length2-1-j])
                tmp[length1 + length2 - 1 - i - j] += d1 * d2

        carry = 0
        for i in range(length1+length2):
            cur = tmp[length1+length2-1-i] + carry
            digit = cur % 10
            carry = cur / 10
            result = str(digit) + result

        if carry != 0:
            result = str(carry) + result
        while result[0] == "0":
            if result == "0":
                break
            result = result[1:]
        return result

Reference