[LeetCode] Multiply Strings | 大整数字符串乘法

https://leetcode.com/problems/multiply-strings/?tab=Description

模拟我们平时做多位乘法的操作，依次把一个乘数与另一个乘数的每一位分别相乘，最后加和。

class Solution { public:string multiply(string num1, string num2) {if (num1 == "0" || num2 == "0") return "0";int n1 = num1.size(), n2 = num2.size();string ret = "0", zeros = "";for (int i = n2 - 1; i >= 0; --i) {// compute num1 * nums2[i]string numi = "";int fac = num2[i] - '0', carry = 0;for (int j = n1 - 1; j >= 0; --j) {carry += (num1[j] - '0') * fac;numi = to_string(carry % 10) + numi;carry /= 10;}if (carry != 0) numi = to_string(carry) + numi;numi += zeros; zeros += "0";// add the resultret = addBinary(ret, numi);}return ret;}string addBinary(string a, string b) {int p1 = a.size() - 1, p2 = b.size() - 1, carry = 0;string ret = "";while (true) {if (p1 >= 0) carry += (a[p1--] - '0');if (p2 >= 0) carry += (b[p2--] - '0');string next_digit = to_string(carry % 10);carry /= 10;if (p1 >= 0 || p2 >= 0 || carry != 0 || next_digit != "0") {ret = next_digit + ret;} else break;}// remove the prefix '0'int i = 0;while (i < ret.size()) {if (ret[i] != '0') break;i++;}if (ret.empty()) ret = "0";return ret.substr(i, ret.size() - i);} };

其中addBinary函数就是大整数加法(leetcode 67: https://leetcode.com/problems/add-binary/
)。

上面这份代码可以AC。不过，虽然时间复杂度是O(n^2)，但是性能不高(C++ 190ms左右)。

-----懒惰与勤劳的分界线-----

举个例子，看能不能将代码写得更简单些，以乘法324 * 78为例，我们做乘法的方式是：

---------3 2 4
x     7 8
---------2 5 9 2
2 2 6 8
---------
2 5 2 7 2

我们将位数按从右往左的顺序编号为0,1,2... 观察结果：

• 第0位 = 4 * 8（除去进位），在两个乘数的位置是(0, 0)
• 第1位 = 2 * 8 + 4 * 7 + 结果第0位的进位（后除去进位），分别在两个乘数的位置是(1, 0), (0, 1)
• 第2位 = 3 * 8 + 2 * 7 + 结果第1位的进位（后除去进位），分别在两个乘数的位置是(2, 0), (1, 1)
• 第3位 = 3 * 7 + 结果第2位的进位（后除去进位），在两个乘数的位置是(2, 1)
• 第4位 = 第3位的进位

规律：结果的第i位 = 两个乘数位置相加恰好为i的数位乘积的加和，再加上结果第i-1位的进位。

实现上，可以用一个int数组mul（大小为两个乘数数位长度之和）存放数位乘积，按mul[i+j] += (num1[i] * num2[j])，然后再把进位算进去，构造出最后的结果。

class Solution { public:string multiply(string num1, string num2) {if (num1 == "0" || num2 == "0") return "0";reverse(num1.begin(), num1.end());reverse(num2.begin(), num2.end());int n1 = num1.size(), n2 = num2.size();vector<int> mul(n1 + n2, 0);for (int i = 0; i < n1; ++i) {int mul1 = num1[i] - '0';for (int j = 0; j < n2; ++j) {mul[i+j] += mul1 * (num2[j] - '0');}}string ret = "";int carry = 0;for (int i = 0; i < mul.size(); ++i) {carry += mul[i];ret = to_string(carry % 10) + ret;carry /= 10;}if (carry != 0) ret = to_string(carry) + ret;// remove the prefix '0'int i = 0;while (i < ret.size() && ret[i] == '0') i++;return ret.substr(i, ret.size() - i);} };

上面这份代码的时间复杂度依然是$O(n^2)$，但是跑leetcode的所有数据降到了10ms左右，性能明显提升。

另外值得一提的是，大数乘法可以通过Fast Fourier Transform(FFT)算法计算多项式乘积将复杂度降到O(n logn)，而FFT则是基于分治的思想，这里就不深入下去了。