MEDIUM

Multiply Strings

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

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

Example

Input:

num1 = "123", num2 = "456"

Output:

"56088"

Explanation:
123 × 456 = 56088.

Constraints

1 ≤ num1.length, num2.length ≤ 200
num1 and num2 consist of digits only.
Both num1 and num2 do not contain any leading zero, except the number 0 itself.

Solution: Elementary Math

Time Complexity: O(m * n), where m and n are the lengths of num1 and num2.
Space Complexity: O(m + n)

C++

class Solution {
public:
    string multiply(string num1, string num2) {
        int n1 = num1.size(), n2 = num2.size();
        vector<int> temp(n1+n2, 0);
        for (int i = n1-1; i >= 0; i--) {
            for (int j = n2 - 1; j >= 0; j--) {
                int offset = (n1 - 1 - i + n2 - 1 - j);
                int val = (num1[i] - '0') * (num2[j] - '0') + temp[offset];
                temp[offset] = val%10;
                temp[offset+1] += val/10;
            }
        }
        string ans;
        for (auto it = temp.begin(); it != temp.end(); it++) ans += to_string(*it);
        while(ans.size() && ans.back() == '0') ans.pop_back();
        reverse(ans.begin(), ans.end());
        return ans.size() ? ans : "0";
    }
};