43.Multiply Strings

Tags: Medium Math String

Links: https://leetcode.com/problems/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.

Example 1:

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

Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"

Note:

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

---

class Solution {
    vector<int> v1, v2, res;

public:
    void init(vector<int> & v, string & s)
    {
        int len = s.size();
        v[0] = len;
        for (int i = 1; i <= len; ++i)
            v[i] = s[len - i] - '0';
    }

    string multiply(string num1, string num2) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        v1.resize(225);
        v2.resize(225);
        res.resize(225);

        init(v1, num1);
        init(v2, num2);

        for (int i = 1; i <= v1[0]; ++i) {
            int extra = 0;
            for (int j = 1; j <= v2[0]; ++j) {
                res[i + j - 1] += v1[i] * v2[j] + extra;
                extra = res[i + j - 1] / 10;
                res[i + j - 1] %= 10;
            }
            res[i + v2[0]] = extra;
        }
        int len = v1[0] + v2[0];
        while (len > 1 && res[len] == 0) --len;

        string s;
        for (int i = len; i >= 1; --i)
            s.push_back('0' + res[i]);

        return s;
    }
};

高精度运算，已经在高精度运算和进制转换总结过了。