Multiply Strings

Problem Statement

You are given two strings num1 and num2 that represent non-negative integers.

Return the product of num1 and num2 in the form of a string.

Assume that neither num1 nor num2 contain any leading zero, unless they are the number 0 itself.

Note: You can not use any built-in library to convert the inputs directly into integers.

Example 1:

Input: num1 = "3", num2 = "4"
Output: "12"

Example 2:

Input: num1 = "111", num2 = "222"
Output: "24642"

Constraints:

  • 1 <= num1.length, num2.length <= 200
  • num1 and num2 consist of digits only.

You should aim for a solution with O(m * n) time and O(m + n) space, where m and n are the lengths of the input strings.

Hint 1

Consider the elementary school method of multiplication. How can you simulate this process with strings?

Hint 2

Each digit in num1 must be multiplied by each digit in num2.

Hint 3

Think about how to manage carries when multiplying and adding the intermediate products.

Solution

Multiplication & Addition

def multiply(num1: str, num2: str) -> str:
if num1 == "0" or num2 == "0":
return "0"
if len(num1) < len(num2):
return multiply(num2, num1)
res, zero = "", 0
for i in range(len(num2) - 1, -1, -1):
cur = _mul(num1, num2[i], zero)
res = _add(res, cur)
zero += 1
return res
def _mul(s: str, d: str, zero: int) -> str:
i, carry = len(s) - 1, 0
d = int(d)
cur = []
while i >= 0 or carry:
n = int(s[i]) if i >= 0 else 0
prod = n * d + carry
cur.append(str(prod % 10))
carry = prod // 10
i -= 1
return ''.join(cur[::-1]) + '0' * zero
def _add(num1: str, num2: str) -> str:
i, j, carry = len(num1) - 1, len(num2) - 1, 0
res = []
while i >= 0 or j >= 0 or carry:
n1 = int(num1[i]) if i >= 0 else 0
n2 = int(num2[j]) if j >= 0 else 0
total = n1 + n2 + carry
res.append(str(total % 10))
carry = total // 10
i -= 1
j -= 1
return ''.join(res[::-1])

Time complexity: O(min(m, n) * (m + n)) Space complexity: O(m + n)

Where m is the length of the string num1 and n is the length of the string num2.