題目描述:給定兩個以字串表示的非負整數 num1 和 num2,回傳它們乘積的字串形式。不可直接將字串轉為整數類型進行計算。
解題思路:模擬小學長乘法(Grade-school Multiplication)。關鍵觀察:num1[i] 與 num2[j] 的乘積,其結果會落在輸出陣列的第 i+j(高位)和 i+j+1(低位)的位置。
演算法步驟:
m+n 的整數陣列 pos(m、n 分別為兩字串長度),初始為 0。pos[i+j+1] += (num1[i]-'0') * (num2[j]-'0')。pos[k] += pos[k+1] / 10; pos[k+1] %= 10;。此方法不需要大數函式庫,純粹模擬手算過程。
時間複雜度:O(m × n) — 兩層巢狀迴圈,m 和 n 分別為兩字串的長度;處理進位需額外 O(m+n),整體仍為 O(m × n)。
空間複雜度:O(m + n) — 儲存中間結果的整數陣列長度為 m+n。
1. m = len(num1), n = len(num2)
2. Create integer array pos of size m+n, all zeros
3. For i from m-1 down to 0:
For j from n-1 down to 0:
mul = digit(num1[i]) * digit(num2[j])
p1 = i+j, p2 = i+j+1
sum = mul + pos[p2]
pos[p2] = sum % 10
pos[p1] += sum / 10
4. Build result string from pos[], skipping leading zeros
5. Return result if non-empty, else "0"逐位相乘後字串大數加法 O(m × n):對 num2 的每一位與整個 num1 相乘,得到多個中間字串結果,再逐一執行字串大數加法。邏輯與長乘法相同,但分兩個獨立步驟實作(乘法 + 加法),程式碼較長且常數因子較大。
FFT 快速乘法 O((m+n) log(m+n)):使用快速傅立葉變換(FFT)或數論變換(NTT)實作多項式乘法,進而計算大數乘法。在 m、n 極大時優於 O(m×n),但實作複雜度高,對本題的輸入規模(≤200 位)沒有必要。