leetcode 43. 字符串相乘

题目

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

原题链接：https://leetcode.cn/problems/multiply-strings/description/

示例 1:
输入: num1 = “2”, num2 = “3”
输出: “6”
示例 2:
输入: num1 = “123”, num2 = “456”
输出: “56088”

思路

把乘法的过程，进行拆解。
如 123 x 456，拆成 123 x 6 x 10 ^0 + 123 x 5 x 10^1 + 123 x 4 x 10^2。
这里除了处理乘法项的相乘过程之外，还要处理每一个乘法项的相加过程。
即包括 相乘过程 和 相加过程。
为了避免溢出，这里每一个过程都得处理成字符串的形式。

• 复杂度分析
  • 时间复杂度 O(mn)。乘法部分两个for循环是 m * n。
  • 空间复杂度 O(m+n)。空间复杂度取决于两个数字的长度。

代码

class Solution {
public:
string multiply(string num1, string num2) {
if (num1 == "0" || num2 == "0") return "0";
string result = "0";
int n = num2.size(), m = num1.size();
for (int i = n - 1; i >= 0; i--) {
string cur;
int add = 0;
int y = num2[i] - '0';
for (int j = m - 1; j >= 0; j--) {
int x = num1[j] - '0';
int res = x * y + add;
char temp = res % 10 + '0';
cur = temp + cur;
add = res / 10;
}
if (add > 0) {
char temp = add + '0';
cur = temp + cur;
}
for (int k = n - i - 1; k > 0; k--) {
cur = cur + '0';
}
result = add_string(result, cur);
}
return result;
}
string add_string(string& num1, string& num2) {
int i = num1.size() - 1;
int j = num2. size() - 1;
int add = 0;
string result = "";
while (i >= 0 || j >= 0 || add > 0) {
int x = i >= 0 ? num1[i] - '0' : 0;
int y = j >= 0 ? num2[j] - '0' : 0;
int res = x + y + add;
char temp = res % 10 + '0';
result = temp + result;
add = res / 10;
i--;
j--;
}
return result;
}
};