Multiply Strings

Problem Id: 43 Difficulty: Medium Tag: Math Tag: String


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])