给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

说明：

1. num1 和 num2 的长度小于110。
2. num1 和 num2 只包含数字 0-9。
3. num1 和 num2 均不以零开头，除非是数字 0 本身。
4. 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

Solution

参考：@labuladong

• 整个计算过程大概是这样，有两个指针 i，j 在 num1 和 num2 上游走，计算乘积，同时将乘积叠加到 res 的正确位置。
• num1[i] 和 num2[j] 的乘积对应的就是 res[i+j] 和 res[i+j+1] 这两个位置。

class Solution {
public:
    string multiply(string num1, string num2) {
        int n1 = num1.size(), n2 = num2.size();
        string s(n1 + n2, '0');     // 初始化大小 n1+n2
        for (int i = n1-1; i >= 0; --i) {
            for (int j = n2-1; j >= 0; --j) {
                int x = num1[i] - '0';
                int y = num2[j] - '0';
                int z = x * y + (s[i+j+1] - '0');  // 累加之前的结果

                s[i+j+1] = z % 10 + '0';    // =
                s[i+j] += z / 10;           // +=
            }
        }
        int pos = 0;
        for (; pos < n1+n2-1; ++pos) {
            if (s[pos] != '0') break;
        }
        return s.substr(pos);
    }
};

• 手动模拟

class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1.size() == 0 || num2.size() == 0) 
            return num1.size() ? num1 : num2;
        string num;

        for (int i = num1.size()-1; i >= 0; --i) {
            int a = (num1[i] - '0');

            string tmp = "";
            // 移位操作
            for (int j = num1.size()-1; j > i; --j) {
                tmp.push_back('0');
            }
            int carry = 0;
            for (int j = num2.size()-1; j >= 0; --j) {
                int m = a * (num2[j] - '0') + carry;
                tmp.insert(0, to_string(m % 10));
                carry = m / 10;
            }
            if (carry) tmp.insert(0, to_string(carry));
            num = addStrings(num, tmp);
        }

        // 处理前导 0
        int pos;
        for (pos = 0; pos < num.size()-1; ++pos) {
            if (num[pos] != '0') break;
        }
        return num.substr(pos);
    }

    string addStrings(string& a, string& b) {
        int n1 = a.size();
        int n2 = b.size();
        if (n1 == 0 || n2 == 0) return n1 ? a : b;

        string num;
        int i = n1 - 1, j = n2 - 1, carry = 0;
        while (i >= 0 || j >= 0) {
            int x = i >= 0 ? a[i--] - '0' : 0;
            int y = j >= 0 ? b[j--] - '0' : 0;
            int sum = (x + y) + carry;
            carry = sum / 10;
            num.insert(0, to_string(sum % 10));
        }
        if (carry) num.insert(0, to_string(carry));
        return num;
    }
};