今天是紀錄LeetCode解題的第四十三天

第四十三題題目：Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

給定兩個非負整數num1和num2用字串表示，傳回num1和num2的乘積，也用字串表示

注意：不得使用任何內建的BigInteger函式庫，也不得直接將輸入轉換為整數

解題思路

定義result儲存每位數字(要存幾位數字為num1+num2的長度，假設三位數乘兩位數最大999*99為5位數)，接著分別用i、j遍歷num1和num2，從個位數開始做乘積，並且算出p1 = i + j(要存放十位數在result中的位置)，p2 = i + j + 1(個位數位置)，接著算個位數位置為乘積 % 10，十位數為乘積//10，依此類推下一次計算就是百位數和十位數

程式碼

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        m,n = len(num1),len(num2)
        t1 = 0
        t2 = 0
        for i in range(0,m):
            t1 = t1 * 10 + (ord(num1[i]) - ord('0'))
        for j in range(0,n):
            t2 = t2 * 10 + (ord(num2[j]) - ord('0'))
        return str(t1*t2)

上面這個算偷懶方法，不過通過這題了，以下我們看一位一位乘的方式，適用於數字很大超過存取位元的時候

class Solution:
    def multiply(self, num1: str, num2: str) -> str:        
        if num1 == "0" or num2 == "0":
            return "0"

        m, n = len(num1), len(num2)
        result = [0] * (m + n)

        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                mul = (ord(num1[i]) - ord('0')) * (ord(num2[j]) - ord('0'))
                p1 = i + j
                p2 = i + j + 1
                s = mul + result[p2]
                result[p2] = s % 10
                result[p1] += s // 10

        result_str = ''.join(str(x) for x in result).lstrip('0')
        return result_str or "0"