算法

(模拟) $O(n*m)$

大整数乘法实际上可以转化为大整数加法

参照乘法的竖式计算方法，用num1每一位去乘num2，然后将这些值按位相加

最后处理进位，然后将答案翻转

C++ 代码

class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") {
            return "0";
        }
        int n = num1.length() + num2.length(); 
        vector<int> res(n,0);
        // 模拟乘法竖式计算
        for (int i = num1.size() - 1; i >= 0; i--) {
            for (int j = num2.size() - 1; j >= 0; j--) {
                res[i + j + 1] += (num1[i] - '0') * (num2[j] - '0');
            }
        }
        // 处理进位
        for (int i = n - 1; i > 0; i--) {
            res[i - 1] += res[i] / 10;
            res[i] %= 10;
        }
        // 将数组转换为字符串
        string ans;
        for (int i = 0; i < n; i++) {
            if (res[i] == 0 && ans.empty()) { // 处理前导零
                continue;
            } 
            ans += char(res[i] + '0');
        }
        return ans;
    }
};

Java 代码

class Solution {
    public String multiply(String num1, String num2) {
        if ("0".equals(num1) || "0".equals(num2)) return "0";

        char[] s1 = new StringBuilder(num1).reverse().toString().toCharArray();
        char[] s2 = new StringBuilder(num2).reverse().toString().toCharArray();

        int n1 = s1.length;
        int n2 = s2.length;

        int[] p = new int[n1 + n2];
        for (int i = 0; i < n1; ++i) {
            for (int j = 0; j < n2; ++j) {
                p[i + j] += (s1[i] - '0') * (s2[j] - '0');
            }
        }

        // 进位
        int d = 0;
        for (int i = 0; i <= n1 + n2 - 2; ++i) {
            p[i] += d;
            d = p[i] / 10;
            p[i] %= 10;
        }
        p[n1 + n2 - 1] = d;

        StringBuilder sb = new StringBuilder();
        for (int i = n1 + n2 - 1; i >= 0; --i) {
            if (sb.length() == 0 && p[i] == 0) continue;
            sb.append((char)(p[i] + '0'));
        }

        return sb.toString();
    }
}