43. Multiply Strings - Explanation

Description

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.

Recommended Time & Space Complexity

You should aim for a solution with O(m*n) time and O(m+n) space, where m is the length of the string num1 and n is the length of the string num2.

Hint 1

Implement a helper function that takes two number strings and returns their sum. Ensure that the length of num1 is greater than num2, swapping them if necessary. Can you think of a way to multiply the strings? Maybe you should first consider basic multiplication, where num1 is multiplied by each digit of num2.

Hint 2

When multiplying num1 with each digit of num2, we iterate through num2 in reverse order. Based on the digit's position, we pad zeros to the multiplication result accordingly—no padding for the last digit, one zero for the second last, and so on. What should be the next step after each multiplication? Maybe you should implement a helper function to handle this.

Hint 3

We implement a helper function that takes num1, a digit, and a variable zeroes, returning the multiplication result with zeroes padded at the end. A global string res stores the final result.

Hint 4

In the main function, we iterate through num2 in reverse order, calling the helper function to multiply num1 with the current digit and append the appropriate number of padding zeros. We then call another helper function that takes this multiplication result and the global result string res, adds them, and updates res.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Multiplication & Addition

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

        if len(num1) < len(num2):
            return self.multiply(num2, num1)

        res, zero = "", 0
        for i in range(len(num2) - 1, -1, -1):
            cur = self.mul(num1, num2[i], zero)
            res = self.add(res, cur)
            zero += 1

        return res

    def mul(self, 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(self, 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 & Space Complexity

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$ .

2. Multiplication

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if "0" in [num1, num2]:
            return "0"

        res = [0] * (len(num1) + len(num2))
        num1, num2 = num1[::-1], num2[::-1]
        for i1 in range(len(num1)):
            for i2 in range(len(num2)):
                digit = int(num1[i1]) * int(num2[i2])
                res[i1 + i2] += digit
                res[i1 + i2 + 1] += res[i1 + i2] // 10
                res[i1 + i2] = res[i1 + i2] % 10

        res, beg = res[::-1], 0
        while beg < len(res) and res[beg] == 0:
            beg += 1
        res = map(str, res[beg:])
        return "".join(res)

Time & Space Complexity

Time complexity: $O(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$ .