題目網址：https://leetcode.cn/problems/multiply-strings/

題意：給兩個以 string 表示的非負整數 num1 和 num2, 返回 num1 和 num2 的乘積 (以 string 表示)。

注意：不得使用任何內建的 BigInteger library 或是 直接將 input string 轉換為整數。

Solution：

想法：利用大數乘法, 用整數 array digits 來儲存乘積

e.g. num1 = "123", num2 = "45"

  • 令每個數最左邊的數 idx = 0, 每往右一位 idx + 1, digits 最左邊的 idx 也為 0
    • num1 中 2 的 idx = 1
    • num2 中 4 的 idx = 0
  • 若 num1.size() = m, num2.size() = n, 則 digits.size() = m + n
    • 若 num1 和 num2 都取最小值, 則 num1 為 $10^{m-1}$, num2 為 $10^{n-1}$
      ➔ num1 x num2 為 $10^{m + n - 2}$, 因此乘積的長度 = m + n - 1
    • 若 num1 和 num2 都取最大值, 則 num1 為 $10^m-1$, num2 為 $10^n-1$
      ➔ num1 x num2 為 $10^{m + n} - 10^m - 10^n + 1$
      ➔ $10^{m + n - 1}$ < 乘積 < $10^{m + n}$, 因此乘積的長度 = m + n
  • 由上述得知 num1 x num2 的長度最多為 m + n
  • num1 中 2 的 idx = 1, 和 num2 中 4 的 idx = 0, 計算出來的 08 會在 digits 的 index 為 [i + j, i + j + 1] 的區間
  • 計算 digits 是先計算 idx = i + j + 1, 因為 i + j + 1 較靠右 (平時我們做乘法加總時的順序), 然後才讓靠左的 i + j 加總 carry
  • 下圖 123 x 45 會得出 digits 為 05535
    • 要先去掉左邊開頭為 0 的部分 (leading zero)
    • 再把剩餘的部分轉成 string, 得到 5535

class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") {
            return "0";
        }

        const int m = num1.size(), n = num2.size();
        vector<int> digits(m + n, 0);

        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                digits[i + j + 1] += (num1[i] - '0') * (num2[j] - '0');
                digits[i + j] += (digits[i + j + 1] / 10);
                digits[i + j + 1] %= 10;
            }
        }

        int i = 0;
        string res;

        // 去掉開頭的 0(leading zero)
        while (digits[i] == 0) {
            ++i;
        }

        while (i < digits.size()) {
            res += to_string(digits[i++]);
        }

        return res;
    }
};
  • time：$O(m \cdot n)$ ➔ for loop
  • space：$O(m + n)$ ➔ digits