Multiply Strings

Intuition

This problem can be splitted into several simple problems.

1. Add 2 big integer.
2. Multiply one big integer with 0-9.

Then we can solve this problem by multiply each number in num1 with num2, and then add the result together.

Solution

``````
class Solution:
def multiply(self, num1: str, num2: str) -> str:
if num1 == '0' or num2 == '0':
return '0'

self._charMultiplyCache = {}
self._singleMultiplyCache = {}
res = '0'
for i, c in enumerate(num1):
res = self._add(res, self._singleMultiply(c, num2) + ('0' * (len(num1) - i - 1)))
return res

def _charMultiply(self, c1, c2):
return (ord(c1) - 48) * (ord(c2) - 48)

def _singleMultiply(self, c, num):
if c not in self._singleMultiplyCache:
res = []
tmp = 0
for c2 in num[::-1]:
tmp += self._charMultiply(c, c2)
res.append(chr(tmp % 10 + 48))
tmp //= 10
if tmp:
res.append(chr(tmp + 48))
self._singleMultiplyCache[c] = ''.join(res[::-1])
return self._singleMultiplyCache[c]

def _add(self, num1, num2):
num1, num2 = num1[::-1], num2[::-1]
res = []
i, j = 0, 0
tmp = 0
while i < len(num1) or j < len(num2):
if i < len(num1):
tmp += ord(num1[i]) - 48
i += 1
if j < len(num2):
tmp += ord(num2[j]) - 48
j += 1
res.append(chr(tmp % 10 + 48))
tmp //= 10
if tmp:
res.append(chr(tmp + 48))
return ''.join(res[::-1])

``````