Leetcode 43: Multiply Strings

1. Problem Statement (Simple Explanation):

You’re given two non-negative integers num1 and num2 as strings.

You must:

• Return their product as a string.

• You cannot:

• Use built-in big integer libraries.

• Convert the entire strings directly to integers.

Lengths:

• 1 <= len(num1), len(num2) <= 200

• Digits only, no leading zero except "0" itself.

2. Examples:

Example 1:

Input: num1 = "2", num2 = "3"

2 * 3 = 6

Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"

123 * 456 = 56088

Output: "56088"

3. Intuition – Simulate Grade-School Multiplication:

We multiply like on paper:

For num1 = "123", num2 = "456":

   1 2 3

x    4 5 6

---------

     7 3 8   (123 * 6, shifted by 0)

   6 1 5     (123 * 5, shifted by 1)

 4 9 2       (123 * 4, shifted by 2)

---------

 5 6 0 8 8

But instead of summing separate rows, we can directly use indexing into an array of size m + n, where m = len(num1), n = len(num2).

Indexing Trick:

Let:

• i index in num1 from right to left (least significant digit).

• j index in num2 from right to left.

If:

• num1[i] contributes a = digit(num1[i])

• num2[j] contributes b = digit(num2[j])

Then:

• The product a * b contributes to positions:

p1 = i + j

p2 = i + j + 1

in a result array of length m + n.

We accumulate multiplication and carry:

sum = a*b + result[p2]

result[p2] = sum % 10

result[p1] += sum / 10

At the end, result holds digits (possibly with leading zeros), and we build the string skipping leading zeros.

4. Algorithm (Step-by-Step):

1. If either num1 == "0" or num2 == "0", return "0".

2. Let:

m = len(num1)

n = len(num2)

result = int array of size m + n, initialized to 0

3. Loop over digits from right to left:

for i from m-1 down to 0:

    for j from n-1 down to 0:

        a = num1[i] - '0'

        b = num2[j] - '0'

        mul = a * b

        p1 = i + j

        p2 = i + j + 1

        sum = mul + result[p2]

        result[p2] = sum % 10

        result[p1] += sum / 10

4. Convert result array to string:

• Skip leading zeros.

• Append digits to a builder.

5. If after skipping zeros, the string is empty → return "0", otherwise return the built string.

Pseudo-code:

Complexity:

Let:

• M = |num1|, n = |num2|

Then:

• Time: O(m*n) – nested loops.

• Space: O(m + n) for the result array.

Given m, n <= 200, this is efficient.

5. Java code:

6. C code:

7. C++ code:

8. Python code:

9. JavaScript code: