给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"
示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/multiply-strings
解题思路
借助中学的竖式乘法
image.png
先判断, 有一个为0则返回"0"
借助一个暂存结果的数组, 保存竖式乘法运算中每一个位置的结果
随后用两层循环遍历两个字符串, 取出当前被遍历的数字, 依次计算结果, 填到数组对应的位置
for (int i = 0; i < len2; i++) {
for (int j = 0; j < len1; j++) {
result[i + j + 1] += (num1.charAt(j) - '0') * (num2.charAt(i) - '0');
}
}
两个数相乘的结果的最大位数 = 两个数的位数之和
举例 98 * 7, 遍历两个字符, 用索引 i 遍历 7, 索引 j 遍历 98
j = 0, i = 0 时 9 * 7 = 63 应该填到 (i + j + 1) 的位置也就是索引 1 的位置
然后 j = 1, i = 0 时 8 * 7 = 56, 填到索引 2 的位置
结束后数组为 [0, 63, 56]
然后从后往前遍历数组, 将每一位的十位数加到前一位, 再将本位只保留下个位数
result[i - 1] += result[i] / 10;
result[i] %= 10;
最后拼接字符串即可, 要注意忽略最开始的"0"
代码
class Solution {
public String multiply(String num1, String num2) {
// 如果有一个是0则返回0
if ("0".equals(num1) || "0".equals(num2)) {
return "0";
}
int len1 = num1.length();
int len2 = num2.length();
int[] result = new int[len1 + len2];
for (int i = 0; i < len2; i++) {
for (int j = 0; j < len1; j++) {
result[i + j + 1] += (num1.charAt(j) - '0') * (num2.charAt(i) - '0');
}
}
// 整理答案
for (int i = result.length - 1; i > 0; i--) {
result[i - 1] += result[i] / 10;
result[i] %= 10;
}
// 拼接字符串
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < result.length; i++) {
// 忽略开头的0
if (i == 0 && result[i] == 0) {
continue;
}
stringBuilder.append(result[i]);
}
return stringBuilder.toString();
}
}
