Multiply Strings

题目描述

大数相乘， A, B

解题方法

这种题目就是模拟人进行乘法运算的过程。

从低位开始相乘，从一个array将A[i]和B[j]的乘积存下来。

要注意的是，人做乘法的时候是从低位开始的，而array表示数字的时候是高位在前 这一点要注意。

• 要从后往前计算
• 最后的结果前面要去0

Solution

class Solution:
    # @param A : string
    # @param B : string
    # @return a strings
    def multiply(self, A, B):
        length_A = len(A)
        length_B = len(B)
        if (length_A == 1 and A == "0") or (length_B == 1 and B == "0"):
            return 0
        if length_A == 1 and A == "1":
            return B
        if length_B == 1 and B == "1":
            return A
        sign = 1
        if A[0] == "-":
            sign *= -1
            A = A[1:]
            length_A -= 1
        if B[0] == "-":
            sign *= -1
            B = B[1:]
            length_B -= 1

        multi_results = [0 for i in range(length_A + length_B)]

        # 要注意是从低位往高位计算
        for i in range(length_A):
            for j in range(length_B):
                num_a = int(A[length_A-1-i])
                num_b = int(B[length_B-1-j])
                multi_results[length_A+length_B-1-(i+j)] += num_a * num_b

        result = ""
        carry = 0
        for k in range(length_A+length_B-1, -1, -1):
            cur_sum = carry + multi_results[k]
            digit = cur_sum % 10
            carry = cur_sum / 10
            multi_results[k] = digit
            result = str(digit) + result
        # 不要忘了carry
        if carry:
            result = str(carry) + result

        # 如果结果前面有0，要将0去掉，因为我们开的array是length_A + leng_B
        # 所以这一步必须
        while result[0] == "0":
            if result == "0":
                break
            result = result[1:]

        return result

Reference