难度: Medium
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
示例 1:
输入: num1 = "2", num2 = "3" 输出: "6"
示例 2:
输入: num1 = "123", num2 = "456" 输出: "56088"
提示：
1 <= num1.length, num2.length <= 200num1 和 num2 只能由数字组成。num1 和 num2 都不包含任何前导零，除了数字0本身。运行时间: 144 ms
内存: 15.1 MB
class Solution:
def multiply(self, num1: str, num2: str) -> str:
if num1 == '0' or num2 == '0':
return '0'
m = len(num1)
n = len(num2)
ans = [0] * (m+n)
for i in range(m-1, -1, -1):
for j in range(n-1, -1, -1):
mul = int(num1[i]) * int(num2[j])
p1 = i + j
p2 = i + j + 1
s = mul + ans[p2]
ans[p1] += s // 10
ans[p2] = s % 10
i = 0
while i < len(ans):
if ans[i] != 0:
break
i += 1
return ''.join([str(x) for x in ans[i:]])
这个题解使用了模拟竖式乘法的方法来计算两个字符串表示的数字相乘的结果。具体做法是： 1. 如果其中一个数字是0，直接返回'0'。 2. 创建一个长度为 m+n 的数组 ans 用于存储计算结果的每一位。 3. 从右往左遍历 num1 和 num2 的每个数字，将对应位置的数字相乘，再加上 ans 数组中对应位置的值。 4. 将乘积的个位数存入 ans 数组的 p2 位置，将十位数加到 p1 位置。 5. 遍历完成后，将 ans 数组转换为字符串，并去除前导0（如果有）。
时间复杂度: O(m*n)
空间复杂度: O(m+n)
class Solution:
def multiply(self, num1: str, num2: str) -> str:
# 如果其中一个数字是0，直接返回'0'
if num1 == '0' or num2 == '0':
return '0'
m = len(num1)
n = len(num2)
# 创建一个长度为 m+n 的数组 ans 用于存储计算结果的每一位
ans = [0] * (m+n)
# 从右往左遍历 num1 和 num2 的每个数字
for i in range(m-1, -1, -1):
for j in range(n-1, -1, -1):
# 将对应位置的数字相乘
mul = int(num1[i]) * int(num2[j])
p1 = i + j
p2 = i + j + 1
# 将乘积加上 ans 数组中对应位置的值
s = mul + ans[p2]
# 将十位数加到 p1 位置
ans[p1] += s // 10
# 将个位数存入 p2 位置
ans[p2] = s % 10
# 去除结果的前导0（如果有）
i = 0
while i < len(ans):
if ans[i] != 0:
break
i += 1
# 将结果转换为字符串并返回
return ''.join([str(x) for x in ans[i:]])
选择从右向左遍历num1和num2是因为这种方式模拟了传统手工乘法的过程。在手工乘法中，我们通常从最低位（右侧）开始计算，逐步向左移动。这样做可以方便地处理进位问题，因为每次乘积只影响当前位和其左侧的一位（即进位位）。如果从左向右遍历，那么处理进位时需要不断调整之前计算的结果，逻辑会更复杂。
每次计算两个数字的某一位的乘积后，需要加上数组ans中对应位置的值，是因为ans数组是用来累积和保存最终的乘积结果的。在乘法中，多个位的乘积可能会影响到同一位置的结果（比如重叠的部分）。即时加上ans数组中的值可以保证这些影响被正确地累加到最终结果中。这种累加的处理保证了每一步的中间结果都正确地反映了之前所有乘积的累积效果，从而保证了最终结果的正确性。
处理乘积结果数组ans中的进位是通过计算每次乘积的十位数和个位数来实现的。具体方法是：将乘积加上当前ans数组对应位置的值后，使用整除10的操作得到十位数（进位），使用取余10的操作得到个位数。然后，将十位数（进位）加到当前位置的前一位（p1位置），个位数更新到当前位置（p2位置）。这样可以保证每次乘积的进位都被正确处理，同时更新对应位置的值。
在去除前导零的过程中，如果遍历完整个结果数组ans后发现所有位都是零，这表明乘积结果为0。处理这种情况的方法是，在将ans数组转换为字符串之前，检查是否所有位都为零（即从数组的起始到终止都没有找到非零元素）。如果是这样，直接返回字符串'0'。这样确保了即使输入的字符串表示的数字非常大，其乘积结果为0时，也能正确地返回'0'。