LeetCode Multiply Strings：大整數乘法的模擬與優化

題目回顧

給定兩個以字符串形式表示的非負整數 num1 和 num2，返回它們的乘積，結果也以字符串形式表示。數字長度可任意大，不可直接轉為內建數值型別。

核心思路：模擬豎式乘法

回想小學數學的豎式乘法：

1. 將兩數反轉，方便按索引對應位權（個位索引 0，十位索引 1...）
2. 建立長度為 len1 + len2 的暫存陣列 temp，因為 m 位數 × n 位數結果至多 m+n 位
3. 雙重迴圈：temp[i+j] += num1[i] * num2[j] 累加同位權乘積
4. 統一處理進位：從低位向高位遍歷 temp，每位取模 10 為當前位，除以 10 為進位
5. 將結果反轉回正序，去除前導零

關鍵細節

• 索引對應：反轉後，num1[i] 對應 10ⁱ 位，num2[j] 對應 10^j 位，乘積自然落在 10^i+j 位，即 temp[i+j]
• 進位處理：先累加所有乘積再統一進位，避免重複進位邏輯
• 前導零：結果最高位可能為 0（如 12×12=144 只有 3 位，但分配了 4 位），需去除

Python 參考實現

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == "0" or num2 == "0":
            return "0"
        
        # 反轉方便索引對應位權
        num1 = num1[::-1]
        num2 = num2[::-1]
        n1, n2 = len(num1), len(num2)
        
        # 暫存陣列，長度最多 n1+n2
        temp = [0] * (n1 + n2)
        
        # 累加同位權乘積
        for i in range(n1):
            for j in range(n2):
                temp[i + j] += int(num1[i]) * int(num2[j])
        
        # 處理進位
        carry = 0
        digits = []
        for val in temp:
            total = carry + val
            carry = total // 10
            digits.append(str(total % 10))
        
        # 反轉回正序，去除前導零
        result = ''.join(digits)[::-1].lstrip('0')
        return result if result else "0"

複雜度分析

• 時間複雜度：O(m×n)，m、n 為兩字符串長度
• 空間複雜度：O(m+n)，暫存陣列與結果字符串

測試用例

if __name__ == "__main__":
    sol = Solution()
    assert sol.multiply("123", "20") == "2460"
    assert sol.multiply("120", "20000") == "2400000"
    assert sol.multiply("0", "3421") == "0"
    assert sol.multiply("999", "999") == "998001"
    print("All tests passed!")

延伸思考

若追求極致效率，可考慮 Karatsuba 算法（O(n^log₂3)）或 FFT 快速傅里葉變換（O(n log n)），但面試中模擬豎式乘法已足夠且工程落地更簡單。