## Description

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"


Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"


Note:

1. The length of both num1 and num2 is < 110.
2. Both num1 and num2 contain only digits 0-9.
3. Both num1 and num2 do not contain any leading zero, except the number 0 itself.
4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

## Solutions

### 1. Math

值得注意的是，提前用一个很长且全零的数组预存好结果，然后算进位和当前位的时候都在这个基础上进行操作。

# Time: O(nm)
# Space: O(n)
class Solution:
def multiply(self, num1: str, num2: str) -> str:
if not num1 or not num2:
return ''
if num1 == '0' or num2 == '0':
return '0'
str_int = dict(zip(list('0123456789')+['10', '11', '12', '13', '14', '15', '16', '17', '18'], range(19)))
int_str = dict(zip(range(19), list('0123456789')+['10', '11', '12', '13', '14', '15', '16', '17', '18']))
l1, l2 = len(num1), len(num2)
res = ['0'] * (l1 + l2)
for i in range(l1-1, -1, -1):
for j in range(l2-1, -1, -1):
# this is crucial
add = str_int[res[i + j + 1]] + str_int[num1[i]] * str_int[num2[j]]
res[i + j + 1] = int_str[add % 10]
res[i + j] = int_str[str_int[res[i + j]] + add // 10]
l = len(res)
for i in range(l):
if res[i] != '0' or i == l - 1:
return ''.join(res[i:])
return ''

# 311/311 cases passed (132 ms)
# Your runtime beats 48.33 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.9 MB)