LeetCode 43：大整數字符串相乘（模擬手算乘法）

題目描述

以字符串形式給定兩個非負整數，返回它們的乘積（也是字符串）。數字可能任意大，不能直接轉換為內建類型。

模擬手算乘法

結果長度最多為 len1 + len2。從右向左逐位相乘，將中間乘積累加到對應位置，最後統一處理進位，再轉為字符串並去除前導零。

代碼實現 (C++)

class Solution {
public:
    string multiply(string num1, string num2) {
        int n1 = num1.size(), n2 = num2.size();
        vector tmp(n1 + n2, 0);
        for (int i = n1 - 1; i >= 0; --i) {
            int a = num1[i] - '0';
            for (int j = n2 - 1; j >= 0; --j) {
                int b = num2[j] - '0';
                tmp[i + j + 1] += a * b;
            }
        }
        for (int i = n1 + n2 - 1; i > 0; --i) {
            tmp[i - 1] += tmp[i] / 10;
            tmp[i] %= 10;
        }
        string res;
        for (int d : tmp) {
            if (!(res.empty() && d == 0)) res.push_back('0' + d);
        }
        return res.empty() ? "0" : res;
    }
};

複雜度

• 時間：O(m*n)，m、n 為字符串長度。
• 空間：O(m+n)。