43

43. Multiply Strings (Medium)

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 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"
Output: "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.

Companies:
Facebook, Microsoft, Apple, Google, Amazon

Related Topics:
Math, String, Simulation

Similar Questions:

• Add Two Numbers (Medium)
• Plus One (Easy)
• Add Binary (Easy)
• Add Strings (Easy)

Solution 1.

// OJ: https://leetcode.com/problems/multiply-strings/
// Author: github.com/lzl124631x
// Time: O(MN)
// Space: O(M + N)
class Solution {
    string mul(const string &a, int n, int shift) {
        if (n == 0 || a == "0") return "0";
        int carry = 0;
        string ans;
        for (int N = a.size(), i = N - 1; i >= 0 || carry;) {
            if (i >= 0) carry += (a[i--] - '0') * n;
            ans += carry % 10 + '0';
            carry /= 10;
        }
        reverse(begin(ans), end(ans));
        while (shift--) ans += '0';
        return ans;
    }
    string add(string a, string b) {
        if (a == "0") return b;
        if (b == "0") return a;
        string ans;
        for (int i = a.size() - 1, j = b.size() - 1, carry = 0; i >= 0 || j >= 0 || carry; ) {
            if (i >= 0) carry += a[i--] - '0';
            if (j >= 0) carry += b[j--] - '0';
            ans += carry % 10 + '0';
            carry /= 10;
        }
        reverse(begin(ans), end(ans));
        return ans;
    }
public:
    string multiply(string a, string b) {
        string ans = "0";
        for (int i = 0, N = b.size(); i < N; ++i) {
            ans = add(ans, mul(a, b[N - 1 - i] - '0', i));
        }
        return ans;
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/multiply-strings/
// Author: github.com/lzl124631x
// Time: O(M * N)
// Space: O(M + N)
class Solution {
public:
    string multiply(string a, string b) {
        int M = a.size(), N = b.size();
        string ans(M + N, '0');
        for (int j = N - 1; j >= 0; --j) {
            int carry = 0;
            for (int i = M - 1, k = N - 1 - j; i >= 0 || carry; ++k) {
                if (i >= 0) carry += (a[i--] - '0') * (b[j] - '0');
                carry += ans[k] - '0';
                ans[k] = carry % 10 + '0';
                carry /= 10;
            }
        }
        while (ans.size() > 1 && ans.back() == '0') ans.pop_back();
        reverse(begin(ans), end(ans));
        return ans;
    }
};