LeetCode Multiply Strings

LeetCode解題之Multiply Strings

原題

將兩個用字符串表示的數進行乘法操作並返回字符串結果。

注意點：

例子：

輸入: num1 = “123”, num2 = “20”
輸出: “2460”

解題思路

根據筆算乘法的公式來看，乘法操作分解開來其實就是先進行每個位的乘法操作，然後將所有結果進行加法操作。首先明確一個m位的數乘以一個n位的數做多為m+n位（都是9的時候試一下）。其次後面的0相等的數在相加時是末尾對齊的。如123×456，我們可以看到1×6、2×5和3×4在進行加法的時候是末尾對齊的，我們可以在進行第一輪乘法的時候將這些數先加起來，而後面的零通過在列表中的位置來表示。再用一個循環進行進位加法，最後把開頭多余的0去掉。具體步驟看下面的例子：

123*456

100        400
 20         50
  3          6

[3*6, 2*6+3*5, 1*6+2*5+3*4, 2*4+1*5, 1*4, 0]

[18, 27, 28, 13, 4, 0]

[8, 27+1, 28, 13, 4, 0]

[8, 8, 28+2, 13, 4, 0]

[8, 8, 0, 13+3, 4, 0]

[8, 8, 0, 6, 5, 0]

"880650"-->"056088"

"56088"

AC源碼

class Solution(object):
    def multiply(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        num1 = num1[::-1]
        num2 = num2[::-1]
        length1 = len(num1)
        length2 = len(num2)
        temp = [0 for __ in range(length1 + length2)]
        # Do multiply
        for i in range(length1):
            for j in range(length2):
                temp[i + j] += int(num1[i]) * int(num2[j])
        carry = 0
        digits = []
        # Do plus
        for num in temp:
            s = carry + num
            carry = s // 10
            digits.append(str(s % 10))
        result = "".join(digits)[::-1]
        # Remove the surplus zero
        sub_index = 0
        for i in range(length1 + length2 - 1):
            if result[i] == "0":
                sub_index += 1
            else:
                break
        result = result[sub_index:]
        return result


if __name__ == "__main__":
    assert Solution().multiply("120", "20000") == 2400000
    assert Solution().multiply("0", "3421") == 0

歡迎查看我的Github來獲得相關源碼。