Problem: 43. 字符串相乘

题目描述

思路及解法

1.初始化和结果数组：

1.1.获取 num1 和 num2 的长度。
1.2.初始化一个 int 数组 res，长度为 len1 + len2，用于存储中间计算结果。因为两个数相乘的结果最多是 len1 + len2 位。

2.逐位相乘：

2.1.从两个字符串的最低位（个位）开始逐位相乘。
2.2.计算乘积 mul，对应到结果数组的两个位置 p1 和 p2。p1 是进位位置，p2 是当前位位置。

2.3.将乘积加到 res[p2]，同时处理进位。

3.处理结果数组前导零：遍历 res 数组，跳过前导零，找到第一个非零元素的位置。

4.构建最终结果字符串：

4.1.使用 StringBuilder 将结果数组中的数字逐个转换为字符并拼接成字符串。
4.2.如果结果字符串为空，返回 “0”；否则返回拼接好的字符串。

复杂度

时间复杂度:

$O(M\times N)$;其中$M$是数组num1的长度，$N$是数组num2的长度

空间复杂度:

$O(Ｍ ＋ Ｎ)$

Code

class Solution {/*** Multiply Strings** @param num1 Given array* @param num2 Given array* @return String*/public String multiply(String num1, String num2) {int len1 = num1.length();int len2 = num2.length();// The result has a maximum of len1 + len2 bitsint[] res = new int[len1 + len2];// Multiply digit by digit starting from the ones digitfor (int i = len1 - 1; i >= 0; --i) {for (int j = len2 - 1; j >= 0; --j) {int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');// The product is in the index position of resint p1 = i + j;int p2 = i + j + 1;// Overlay to resint sum = mul + res[p2];res[p2] = sum % 10;res[p1] += sum / 10;}}// Result prefix possible stored 0(unused bits)int i = 0;while (i < res.length && res[i] == 0) {i++;}// Converts the result to a stringStringBuilder str = new StringBuilder();for (; i < res.length; ++i) {str.append((char) ('0' + res[i]));}return str.length() == 0 ? "0" : str.toString();}
}