43. 字符串相乘

二哥瞎逼逼：当你习惯了刷题的节奏，每天不来一道会觉得缺点啥，那今天我们

就来一道 LeetCode 的中等题：字符串相乘。目前秋招正式批正在如火如荼的开

展中，冲啊！下周搞一个星球的打卡活动吧，我翻翻去年的。

题意

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

们的乘积也表示为字符串形式。

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

1 <= num1.length, num2.length <= 200

难度

中等

示例

输入: num1 = "2", num2 = "3"

输出: "6"

输入: num1 = "123", num2 = "456"

输出: "56088"

分析 1

?

结果 ， 哈 哈 。

这道题不让我们使用 BigInteger，我偏要用一下来看看果，哈哈 ? 。

import java.math.BigInteger;

class Solution {

public String multiply(String num1, String num2) {

BigInteger n1 = new BigInteger(num1);

BigInteger n2 = new BigInteger(num2);

return n1.multiply(n2).toString();

}

}

来看一下题解效率：

043.字符串相乘-20240808130634.png

?

还不错嘛，击败了 41.56% 的 Java 说，有时候算法的要求真是很扯明简单解决方案它就不让我们用。?手

。

用

不

就

它

案

方

决

解

明

扯

很

是

真

求

要

的

法

算

候

有

能

只

我

，

但我们不管，先暴力解出来壮壮胆再说。

不过我多瞅了一眼 BigInteger 的 multiply 方法源码，不简单，有数组，有 for 循环，有位运

算。

043.字符串相乘-20240808131016.png

分析 2

来回忆一下小学阶段，我们是怎么做乘法运算的：

043.字符串相乘-20240808131546.png

列竖式，计算每一位的乘积，然后错位相加。这也是我们解决这道题的 “灵丹妙药”。

假如输入是 123 * 456，我们来看一下：

• 7 3 8 的 第 0 位——8 是由 123 的 第 0 位——3 和 456 的 第 0 位——6 相乘并向第 1

位进 1 后得到的；

• 7 3 8 的 第 1 位——3 是由 123 的 第 1 位——2 和 456 的 第 0 位——6 相乘，再加上

一次的进位 1，并向第 2 位进 1 得到的；

• 7 3 8 的 第 2 位——7 是由 123 的 第 2 位——1 和 456 的 第 0 位——6 相乘，再加上

一次的进位 1 得到的（不需要再进位）；

• 6 1 5 的 第 1 位——5 是由 123 的 第 0 位——3 和 456 的 第 1 位——5 相乘并进位得

到的；

• 6 1 5 的 第 2 位——1 是由 123 的 第 1 位——2 和 456 的 第 1 位——5 相乘并进位得

到的；

• …

有没有看出来一点端倪？

两个乘数的长度分别是 m 和 n，那么乘积的长度最多是 m + n。

两个乘数的第 i 位和第 j 位相乘的结果会出现在乘积的第 i + j 位。

我们可以用一个数组来存储每一位的乘积，然后再将数组中的每一位错位相加，最后得到

结果。

当输入是 123 * 456 的时候，我们来简单模拟一下前三个步骤：

043.字符串相乘-20240808145602.png

初始状态的时候，我们可以看到，result 数组的长度是 m + n，每一位都是 0。

第一步，我们计算 3 * 6，得到 18，然后将 8 存储在 result[5]，1 进位存储在 result[4]。

第二步，我们计算 3 * 5，得到 15，加上之前进位的 1 是 16，然后将 6 存储在 result[4]，1

进位存储在 result[3]。

依次类推，我们可以得到最终的结果 56088。来看题解代码：

class Solution {

public String multiply(String num1, String num2) {

int m = num1.length(), n = num2.length();

int[] result = new int[m + n]; // 用于存储最终结果的每一位

// 从右到左遍历 num1 和 num2 的每一位

 for (int i = m - 1; i >= 0; i--) {

for (int j = n - 1; j >= 0; j--) {

int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0'); // 两位数字的乘积

int p1 = i + j, p2 = i + j + 1;

int sum = mul + result[p2]; // 当前乘积加上当前位置已有的值

result[p2] = sum % 10; // 存储个位数

result[p1] += sum / 10; // 处理进位

}

}

// 将结果数组转换为字符串

StringBuilder sb = new StringBuilder();

for (int num : result) {

if (!(sb.length() == 0 && num == 0)) { // 去掉前导零

sb.append(num);

}

}

return sb.length() == 0 ? "0" : sb.toString(); // 处理乘积为 0 的情况

}

public static void main(String[] args) {

Solution solution = new Solution();

System.out.println(solution.multiply("2", "3")); // 输出 "6"

System.out.println(solution.multiply("123", "456")); // 输出 "56088"

}

}

• 双重循环遍历 num1 和 num2 的每一位，计算乘积 mul。

• int p1 = i + j, p2 = i + j + 1：确定乘积在结果数组中的位置。

• int sum = mul + result[p2]：当前乘积加上当前位置已有的值（注意进位）。

• result[p2] = sum % 10：存储当前位。

• result[p1] += sum / 10：处理进位。

这里有三个小技巧：

• 我们可以从字符串的最后一位开始遍历，这样就省去了反转字符串的操作。

• 最后注意要去掉结果数组中的前导零，因为最后一次计算不需要进位的话，会在结果

数组的最高位存储 0。

• char - '0' 可以将字符转换为数字，这个知识点之前应该也讲过。

好，我们来看一下在 Leetcode 上面跑的效率。

043.字符串相乘-20240808151126.png

总结

?真心，我

话，目

。我 种

呀

了

好

就

用

接

直

的

算

法

乘

有

已

得

，

冒

感

很

是

不 对这种 题目 不 是 很 感 冒 ， 觉得 已 有 乘 法 运算 的 话， 直 接 调用 就 好 了 呀 。 ?

但是有时候，算法考察的就是我们的思维能力，或者叫造轮子能力，一道乘法运算的题

目，最终考察的还是我们对数组、for 循环和进位的理解。

以及一些细节处理，比如说去掉前导零。99*99 的结果是 9801，不用考虑 0 的问题；但 11*11 的

结果是 121，按照我们的题解方法数组的千位就是 0，所以我们要去掉。

力扣链接：https://leetcode.cn/problems/multiply-strings/