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.