給定兩個以字串表示的非負整數
num1和num2，回傳它們的乘積（也以字串表示）。不能使用內建的大整數運算庫或直接將輸入轉為整數。
Example:
Input: num1 = “123”, num2 = “456” Output: “56088”
Intuition
TIP
核心思路：模擬手算直式乘法——num1[i] * num2[j] 的結果放在 result[i+j] 和 result[i+j+1] 的位置。
- 兩個長度分別為 m、n 的數字相乘，結果最多 m + n 位
- 手算直式乘法中，num1 第 i 位乘以 num2 第 j 位的乘積，會影響結果的第 i+j 和 i+j+1 位
- 先在陣列中累加所有乘積，最後統一處理進位
Approaches
1. Digit Multiply + Carry — O(m * n) / O(m + n)
- Idea: 模擬直式乘法，每次內層迴圈都處理進位
- Time:
O(m * n)- 雙層迴圈 - Space:
O(m + n)- 結果陣列
class Solution {
fun multiply(num1: String, num2: String): String {
if (num1 == "0" || num2 == "0") return "0"
val m = num1.length
val n = num2.length
val result = IntArray(m + n)
for (i in m - 1 downTo 0) {
for (j in n - 1 downTo 0) {
val mul = (num1[i] - '0') * (num2[j] - '0')
val p1 = i + j
val p2 = i + j + 1
val sum = mul + result[p2]
result[p2] = sum % 10
result[p1] += sum / 10
}
}
val sb = StringBuilder()
for (digit in result) {
if (sb.isEmpty() && digit == 0) continue
sb.append(digit)
}
return if (sb.isEmpty()) "0" else sb.toString()
}
}⭐ 2. Accumulate then Carry Once — O(m * n) / O(m + n)
- Idea: 先將所有乘積累加到對應位置（允許大於 9），最後從低位到高位統一處理進位
- Time:
O(m * n)- 雙層迴圈 - Space:
O(m + n)- 結果陣列
class Solution {
fun multiply(num1: String, num2: String): String {
if (num1 == "0" || num2 == "0") return "0"
val m = num1.length
val n = num2.length
val pos = IntArray(m + n)
// 累加所有乘積
for (i in m - 1 downTo 0) {
for (j in n - 1 downTo 0) {
pos[i + j + 1] += (num1[i] - '0') * (num2[j] - '0')
}
}
// 統一處理進位
var carry = 0
for (i in pos.lastIndex downTo 0) {
val sum = pos[i] + carry
pos[i] = sum % 10
carry = sum / 10
}
val sb = StringBuilder()
for (digit in pos) {
if (sb.isEmpty() && digit == 0) continue
sb.append(digit)
}
return if (sb.isEmpty()) "0" else sb.toString()
}
}Note: Why result[i+j+1] instead of [i+j]?
考慮 num1[i] 和 num2[j]（0-indexed，最高位在前）：
- num1[i] 代表 num1 從高位數來第 i 位，即 10^(m-1-i) 的位置
- num2[j] 代表 10^(n-1-j) 的位置
- 乘積對應 10^(m+n-2-i-j) 的位置
- 在 m+n 長度的結果陣列中，10^k 對應 index = m+n-1-k = i+j+1
所以乘積的低位放在 i+j+1，高位（進位）放在 i+j。
🔑 Takeaways
- Pattern: 大數乘法模擬，掌握 num1[i] * num2[j] 放在 result[i+j+1] 的位置映射
- Key trick: 先累加再統一進位的寫法更乾淨；記得處理前導零和「0」的特殊情況