LeetCode 43: Multiply Strings

Problem Restatement

We are given two non-negative integers num1 and num2, but they are stored as strings.

We need to return their product, also as a string.

We cannot use a built-in big integer library, and we cannot directly convert the whole input strings into integers. The official problem states this string multiplication requirement and restriction directly.

Example:

num1 = "2"
num2 = "3"

The product is:

"6"

Another example:

num1 = "123"
num2 = "456"

The product is:

"56088"

Input and Output

Function shape:

def multiply(num1: str, num2: str) -> str:
    ...

First Thought: Repeated Addition

A simple idea is to add num1 to itself num2 times.

For example:

"12" * "3" = "12" + "12" + "12" = "36"

But this is not practical.

If num2 is very large, repeated addition would take too long. Also, num2 is a string, so we would still need to implement large-number addition manually.

We need a direct multiplication method.

Key Insight

Use the same multiplication method we use by hand.

When multiplying two digits:

num1[i] * num2[j]

their result contributes to a position determined by i and j.

If num1 has length m and num2 has length n, the product has at most m + n digits. This is the standard reason solutions allocate an array of length m + n.

So we create:

result = [0] * (m + n)

Each digit multiplication contributes to two nearby positions:

p1 = i + j
p2 = i + j + 1

The ones digit goes into p2.

The carry goes into p1.

Algorithm

Let:

m = len(num1)
n = len(num2)

Create a result array of size m + n.

Then scan both strings from right to left.

For every pair of digits:

1. Convert the characters to digits.
2. Multiply them.
3. Add the product to the current value at result[i + j + 1].
4. Put the ones digit at result[i + j + 1].
5. Add the carry to result[i + j].

After all multiplications, remove leading zeros.

If the result is empty after removing zeros, return "0".

Walkthrough

Use:

num1 = "123"
num2 = "456"

The result array has length:

3 + 3 = 6

Start with:

[0, 0, 0, 0, 0, 0]

Consider the last digits:

3 * 6 = 18

Here:

i = 2
j = 2
p1 = 4
p2 = 5

Place 8 at index 5 and carry 1 to index 4:

[0, 0, 0, 0, 1, 8]

Next:

3 * 5 = 15

This affects positions 3 and 4.

But index 4 already has 1, so we add into it:

15 + 1 = 16

Put 6 at index 4 and carry 1 to index 3:

[0, 0, 0, 1, 6, 8]

Continuing this process for all digit pairs gives:

[0, 5, 6, 0, 8, 8]

After removing the leading zero, we get:

"56088"

Correctness

Each digit in num1 is multiplied by each digit in num2.

For digits at positions i and j, their place value in the final product is determined by how far they are from the right end of their strings.

Using indices i + j and i + j + 1 places each partial product into the same decimal position that grade-school multiplication would use.

The algorithm adds each partial product into the result array instead of creating separate rows. Carry is handled immediately by splitting the sum into:

sum // 10
sum % 10

The carry moves left, and the ones digit stays in the current position.

Since every digit pair contributes exactly once, and every contribution is placed into the correct decimal position, the final array represents the true product.

Removing leading zeros does not change the numeric value. If all digits are zero, the product is "0".

Complexity

Here, m = len(num1) and n = len(num2).

Implementation

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

        m = len(num1)
        n = len(num2)
        result = [0] * (m + n)

        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                digit1 = ord(num1[i]) - ord("0")
                digit2 = ord(num2[j]) - ord("0")

                product = digit1 * digit2

                p1 = i + j
                p2 = i + j + 1

                total = product + result[p2]

                result[p2] = total % 10
                result[p1] += total // 10

        return "".join(str(digit) for digit in result).lstrip("0")

Code Explanation

We first handle zero:

if num1 == "0" or num2 == "0":
    return "0"

This avoids returning an empty string after stripping leading zeros.

Then we allocate enough space for the answer:

result = [0] * (m + n)

The nested loops visit digit pairs from right to left:

for i in range(m - 1, -1, -1):
    for j in range(n - 1, -1, -1):

Each character is converted into an integer digit:

digit1 = ord(num1[i]) - ord("0")
digit2 = ord(num2[j]) - ord("0")

Then we multiply:

product = digit1 * digit2

The product contributes to these two result positions:

p1 = i + j
p2 = i + j + 1

We add the current product to whatever is already stored at p2:

total = product + result[p2]

Then we store the ones digit and carry:

result[p2] = total % 10
result[p1] += total // 10

Finally, convert the digit array into a string and remove leading zeros:

return "".join(str(digit) for digit in result).lstrip("0")

Testing

def run_tests():
    s = Solution()

    assert s.multiply("2", "3") == "6"
    assert s.multiply("123", "456") == "56088"
    assert s.multiply("0", "999") == "0"
    assert s.multiply("999", "999") == "998001"
    assert s.multiply("1", "12345") == "12345"
    assert s.multiply("100", "100") == "10000"
    assert s.multiply("9133", "0") == "0"

    print("all tests passed")

run_tests()