43. Multiply Strings

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

Problem

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.

Solution

class Solution {
public:
    string multiply(string &num1, string &num2) {
        if (num1 > num2) return multiply(num2, num1);
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        string result;
        for (int i = 0; i < num1.size(); ++i) {
            string temp; int carry = 0;
            for (int j = 0; j < num2.size(); ++j) {
                int pd = (num1[i] - '0') * (num2[j] - '0') + carry;
                const char d = '0' + (pd % 10);
                temp += d;
                carry = pd / 10;
            }
            const char d = '0' + carry;
            temp += d;
            if (result.empty()) {
                result = temp;
            } else {
                result += '0';
                int _carry = 0;
                for (int k = i; k < result.size(); ++k) {
                    int sum = (result[k] - '0') + (temp[k - i] - '0') + _carry;
                    result[k] = '0' + sum % 10;
                    _carry = sum / 10;
                }
            }
        }
        string _result; bool flag = false;
        for (int i = result.size() - 1; i >= 0; --i) {
            if (result[i] != '0') flag = true;
            if (flag) _result += result[i];
        }
        return (_result.empty()) ? "0" : _result;
    }
};

• #math

• #important