【刷题记录】43. 字符串相乘

一、题目描述

来源：力扣（LeetCode）

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

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

示例 1:

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

输出: "6"

示例 2:

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

输出: "56088"

提示：

• 1 <= num1.length, num2.length <= 200
• num1 和 num2 只能由数字组成。
• num1 和 num2 都不包含任何前导零，除了数字0本身。

二丶思路分析

模拟
这道题目不能直接将输入转化为整数，然后计算，那我们可以根据小时候学的数字相乘的竖式计算方法进行模拟。
例如123 * 545

从右往左遍历乘数，将乘数的每一位与被乘数相乘得到对应的结果，再将每次得到的结果累加

注意补0 并且 两个长度分别为 n 和 m 的数相乘，长度不会超过 n + m。

三、代码实现

```

class Solution {

   public String multiply(String n1, String n2) {

       int n = n1.length(), m = n2.length();

       int[] res = new int[n + m];

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

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

               int a = n1.charAt(i) - '0';

               int b = n2.charAt(j) - '0';

               int r = a * b;

               r += res[i + j + 1];

               res[i + j + 1] = r % 10;

               res[i + j] += r / 10;

           }

       }

       StringBuilder sb = new StringBuilder();

       for (int i = 0; i < n + m; i++) {

           if (sb.length() == 0 && res[i] == 0) continue;

           sb.append(res[i]);

       }

       return sb.length() == 0 ? "0" : sb.toString();

   }

}

```

复杂度分析

• 时间复杂度：
  网络异常，图片无法展示

  |
  ，其中 m 和 n分别是num1和 num2的长度
• 空间复杂度：O*(m+n)

运行结果

总结

这个题目其实带我们重温了一下我们小时候学乘法时候学习的乘法计算过程。只要理解了这个计算的过程。这道题目就比较简单了。