43. Multiply Strings

Medium

Description

給定兩個以字串表示的非負整數 num1 和 num2，回傳它們的乘積（也以字串表示）。不能使用內建的大整數運算庫或直接將輸入轉為整數。

Example:

Input: num1 = “123”, num2 = “456” Output: “56088”

Intuition#

核心思路：模擬手算直式乘法——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: 逐位相乘 + 逐步進位#

概念: 模擬直式乘法，每次內層迴圈都處理進位
時間複雜度: O(m * n) - 雙層迴圈
空間複雜度: 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: 先累加再統一進位#

概念: 先將所有乘積累加到對應位置（允許大於 9），最後從低位到高位統一處理進位
時間複雜度: O(m * n) - 雙層迴圈
空間複雜度: 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()
    }
}

補充：為什麼 result[i+j+1] 而不是 [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] 的位置映射
關鍵技巧: 先累加再統一進位的寫法更乾淨；記得處理前導零和「0」的特殊情況