Multiply Strings
題目描述:給定兩個以字串表示的非負整數 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;。
- 跳過最前面的 0,將陣列轉為字串輸出;若全為 0 則回傳 "0"。
此方法不需要大數函式庫,純粹模擬手算過程。
時間複雜度:O(m × n) — 兩層巢狀迴圈,m 和 n 分別為兩字串的長度;處理進位需額外 O(m+n),整體仍為 O(m × n)。
空間複雜度:O(m + n) — 儲存中間結果的整數陣列長度為 m+n。
逐位相乘後字串大數加法 O(m × n):對 num2 的每一位與整個 num1 相乘,得到多個中間字串結果,再逐一執行字串大數加法。邏輯與長乘法相同,但分兩個獨立步驟實作(乘法 + 加法),程式碼較長且常數因子較大。
FFT 快速乘法 O((m+n) log(m+n)):使用快速傅立葉變換(FFT)或數論變換(NTT)實作多項式乘法,進而計算大數乘法。在 m、n 極大時優於 O(m×n),但實作複雜度高,對本題的輸入規模(≤200 位)沒有必要。