题目描述（中等难度）

就是两个数相乘，输出结果，只不过数字很大很大，都是用 String 存储的。也就是传说中的大数相乘。

解法一

我们就模仿我们在纸上做乘法的过程写出一个算法。

个位乘个位，得出一个数，然后个位乘十位，全部乘完以后，就再用十位乘以各个位。然后百位乘以各个位，最后将每次得出的数相加。十位的结果要补 1 个 0 ，百位的结果要补两个 0 。相加的话我们可以直接用之前的大数相加。直接看代码吧。

时间复杂度：O（m * n）。m，n 是两个字符串的长度。

空间复杂度：O（1）。

解法二

上边的解法非常简单粗暴，但是不够优雅。我们看一下从未见过的一种竖式计算。

43. Multiply Strings - 图1

我们把进位先不算，写到对应的位置。最后再统一更新 pos 中的每一位。

而对于运算中的每个结果，可以观察出一个结论。

num1 的第 i 位乘上 num2 的第 j 位，结果会分别对应 pos 的第 i + j 位和第 i + j + 1 位。

例如图中的红色部分，num1 的第 1 位乘上 num2 的第 0 位，结果就对应 pos 的第 1 + 0 = 1 和 1 + 0 + 1 = 2 位。

  2.     if (num1.equals("0") || num2.equals("0")) {
  3.         return "0";
  4.     }
  5.     int n1 = num1.length();
  6.     int n2 = num2.length();
  7.     int[] pos = new int[n1 + n2]; //保存最后的结果
  8.         for (int j = n2 - 1; j >= 0; j--) {
  10.             int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
  11.             //加上 pos[i+j+1] 之前已经累加的结果
  12.             int sum = mul + pos[i + j + 1];
  13.             //更新 pos[i + j]
  14.             pos[i + j] += sum / 10;
  15.             //更新 pos[i + j + 1]
  16.             pos[i + j + 1] = sum % 10;
  17.         }
  18.     StringBuilder sb = new StringBuilder();
  19.     for (int i = 0; i < pos.length; i++) {
  20.         //判断最高位是不是 0 
  21.         if (i == 0 && pos[i] == 0) {
  22.             continue;
  23.         }
  24.         sb.append(pos[i]);
  25.     }
  27. }

时间复杂度：O（m * n）。m，n 是两个字符串的长度。

空间复杂度：O（m + n）。m，n 是两个字符串的长度。

总

如果按普通的思路写，这道题也不难。新的竖式的计算，让人眼前一亮，代码优雅了很多。

添加好友一起进步~

如果觉得有帮助的话，可以点击 给一个 star 哦 ^^