[LeetCode解題攻略] 43. Multiply Strings

題目描述

給定兩個非負整數的字串 num1 和 num2，分別表示兩個數字。要求模擬乘法運算，並返回結果字串，不能使用內建的大數處理函式（例如 Python 的 int 或 BigInteger）。

輸入: num1 = "2", num2 = "3"
輸出: "6"

範例 2：

輸入: num1 = "123", num2 = "456"
輸出: "56088"

限制條件：

1. 1 <= num1.length, num2.length <= 200
2. num1 和 num2 只包含數字，且不包含前導零。

解題思路

關鍵概念

1. 模擬乘法運算：
2. • 手動模擬紙筆計算中數字的逐位相乘。
   • 使用類似「乘法表」的方式，計算每對位數的乘積，並將結果累加在正確位置上。
2. 處理進位：
3. • 當部分乘積超過 10 時，需要進位。

如何進行計算？

1. 假設 num1 長度為 n₁​，num2 長度為 n₂，那麼結果最大長度為 n₁+n₂。
2. 使用一個數組 result 來存放每一位的計算結果。
3. 遍歷 num1 和 num2 的每個位數，模擬逐位相乘的過程，並將計算結果累加到 result 對應的位置。
4. 處理進位，將結果轉為字串。

解法一：模擬逐位相乘

核心步驟

1. 初始化一個長度為 num1.length + num2.length 的陣列 result，用來存放中間結果。
2. 從後往前遍歷 num1 和 num2 的每個位數，計算其乘積並加到對應位置。
3. 處理進位，將結果陣列轉為字串。

程式碼

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

        # 初始化結果數組，長度最多為 num1.length + num2.length
        n1, n2 = len(num1), len(num2)
        result = [0] * (n1 + n2)

        # 倒序遍歷 num1 和 num2
        for i in range(n1 - 1, -1, -1):
            for j in range(n2 - 1, -1, -1):
                # 計算對應位的乘積
                mul = int(num1[i]) * int(num2[j])
                # 確定累加的位置
                pos1, pos2 = i + j, i + j + 1
                # 加入到 result 對應位置
                sum_ = mul + result[pos2]
                result[pos2] = sum_ % 10  # 取餘數存當前位
                result[pos1] += sum_ // 10  # 進位

        # 去掉前導零，轉為字串
        result_str = ''.join(map(str, result)).lstrip('0')
        return result_str

時間與空間複雜度

• 時間複雜度：O(n₁×n₂)，其中 n₁ 和 n₂​ 分別為 num1 和 num2 的長度。
  每位數字需要兩層迴圈進行乘積計算。
• 空間複雜度：O(n₁+n₂)，用於存儲結果數組。

結論

1. 這道題的關鍵在於熟悉數字乘法的模擬過程，並有效處理進位與結果合併。
2. 模擬逐位相乘 是最常見的解法，時間與空間複雜度都滿足題目要求。
3. 如果你對紙筆計算過程較為熟悉，可以嘗試進一步優化代碼結構。

希望這篇文章幫助你深入理解​這道題目的解法！