43. Multiply Strings (Medium)

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

Note:

1. The length of both num1 and num2 is < 110.
2. Both num1 and num2 contains only digits 0-9.
3. Both num1 and num2 does not contain any leading zero.
4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

Solution:

Remember how we do multiplication?

Start from right to left, perform multiplication on every pair of digits, and add them together. Let's draw the process! From the following draft, we can immediately conclude:

num1[i] * num2[j] will be placed at indices [i + j, i + j + 1]

version 1: 9ms

class Solution {
public:
    string multiply(string num1, string num2) {
        string res(num1.size()+num2.size(), '0');

        for (int i = num1.size()-1; i >= 0; --i) {
            int carry = 0;
            for (int j = num2.size()-1; j >= 0; --j) {
                int tmp = (res[i+j+1]-'0')+(num1[i]-'0')*(num2[j]-'0')+carry;
                res[i+j+1] = tmp%10+'0';
                carry = tmp/10;
            }
            res[i] += carry;
        }

        size_t pos = res.find_first_not_of("0");
        if (pos == string::npos) return "0";
        return res.substr(pos);
    }
};

version 2: 9ms

class Solution {
public:
    string multiply(string num1, string num2) {
        vector<int> res(num1.size()+num2.size(), 0);

        for (int i = num1.size()-1; i >= 0; --i) {
            for (int j = num2.size()-1; j >= 0; --j) {
                int tmp = res[i+j+1]+(num1[i]-'0')*(num2[j]-'0');
                res[i+j] += tmp/10;
                res[i+j+1] = tmp%10;
            }
        }

        string ans; int idx = 0;
        while (idx < res.size()-1 && res[idx] == 0) ++idx;

        for (int i = idx; i < res.size(); ++i) ans += res[i]+'0';
        return ans;
    }
};