Multiply Strings

https://leetcode.com/problems/multiply-strings/description/

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

Note:

The length of both num1 and num2 is < 110.

Both num1 and num2 contains only digits 0-9.

Both num1 and num2 does not contain any leading zero.

You must not use any built-in BigInteger library or convert the inputs to integer directly.

Thoughts

给定两个str代表乘数，返回以str表示的结果。乘法是从后开始，num1分别乘以num2的每一位并左移一位，最后相加。num1的第i位和num2第j位所乘结果会叠加到[i + j + 1]和[i + j]位上。因此用一个数组记录下每位叠加的临时结果。这里的每位临时叠加结果不一定是单个数字，也可能是双位，不过最后都会在计算过程中取余进位。

/*
 * @lc app=leetcode id=43 lang=cpp
 *
 * [43] Multiply Strings
 */

// @lc code=start
class Solution {
public:
    string multiply(string num1, string num2) {
        const int M = num1.length(), N = num2.length();
        vector<int> pos(M + N);
        for (int i = M - 1; i >= 0; --i) {
            for (int j = N - 1; j >= 0; --j) {
                int r = (num1[i] - '0') * (num2[j] - '0');
                const int p0 = i + j, p1 = p0 + 1;
                r += pos[p1];
                pos[p1] = r % 10;
                pos[p0] += r / 10;
            }
        }
        string res;
        for (const auto i : pos) {
            if (res.empty() && i == 0) continue;
            res.push_back(i + '0');
        } 
        return res.empty() ? "0" : res;
    }
};
// @lc code=end

时间复杂度O(MN), 空间O(M + N).