LeetCode 43: Multiply Strings Solution in Python Explained

Problem Statement

LeetCode 43, Multiply Strings, is a medium-level problem where you’re given two non-negative integers represented as strings, num1 and num2. Your task is to return their product as a string. You cannot use built-in multiplication or conversion to integers (e.g., int()), and the numbers can be arbitrarily large.

Constraints

1 <= num1.length, num2.length <= 200: String lengths are between 1 and 200.
num1 and num2 consist of digits 0-9.
No leading zeros, except for the number 0 itself.

Example

Input: num1 = "2", num2 = "3"
Output: "6"
Explanation: 2 * 3 = 6.

Input: num1 = "123", num2 = "456"
Output: "56088"
Explanation: 123 * 456 = 56088.

Input: num1 = "0", num2 = "52"
Output: "0"
Explanation: 0 * 52 = 0.

Understanding the Problem

How do you solve LeetCode 43: Multiply Strings in Python? For num1 = "123" and num2 = "456", compute 123 * 456 = 56088, returning "56088" as a string without converting to integers. Mimic manual multiplication: multiply digits, handle carries, and sum results. We’ll explore two approaches: a Digit-by-Digit Multiplication Solution (optimal and primary) and an Alternative with Array Multiplication (intuitive but similar). The digit-by-digit method processes each pair of digits and builds the result efficiently.

Solution 1: Digit-by-Digit Multiplication Approach (Primary)

Explanation

Multiply each digit of num1 by each digit of num2, placing results in an array based on their position (right-to-left). Use the array to handle carries and build the final string. The position of a product num1[i] * num2[j] is i + j + 1 (from the right), with carry at i + j.

Here’s a flow for "123" * "456":

1*6 = 6: [0,0,6]
1*5 = 5: [0,5,6]
1*4 = 4: [4,5,6]
2*6 = 12: [4,6,8]
...
Result: [5,6,0,8,8]

Initialize Result Array.

Size = len(num1) + len(num2).

Multiply Digits.

Compute products, add to positions with carry.

Process Carries.

Propagate carries leftward.

Build String.

Skip leading zeros, return result.

Step-by-Step Example

Example 1: num1 = "123", num2 = "456"

We need "56088".

Goal: Multiply strings to get product.
Result for Reference: "56088".
Start: num1 = "123", num2 = "456", n1 = 3, n2 = 3, result = [0,0,0,0,0,0].
Step 1: i = 2 (3), j = 2 (6).

3*6 = 18, pos = 5, result[5] += 8, result[4] += 1, result = [0,0,0,0,1,8].

Step 2: i = 2 (3), j = 1 (5).

3*5 = 15, pos = 4, result[4] += 5, result[3] += 1, result = [0,0,0,1,6,8].

Step 3: i = 2 (3), j = 0 (4).

3*4 = 12, pos = 3, result[3] += 2, result[2] += 1, result = [0,0,1,3,6,8].

Step 4: i = 1 (2), j = 2 (6).

2*6 = 12, pos = 4, result[4] += 2, result[3] += 1, result = [0,0,1,4,8,8].

Step 5: Continue, full result = [0,5,6,0,8,8].
Step 6: Build string, skip 0, "56088".
Finish: Return "56088".

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

We need "6".

Start: result = [0,0].
Step 1: 2*3 = 6, pos = 1, result = [0,6].
Step 2: Build string, "6".
Finish: Return "6".

How the Code Works (Digit-by-Digit)

Here’s the Python code with line-by-line explanation:

def multiply(num1: str, num2: str) -> str:
    # Line 1: Handle zero cases
    if num1 == "0" or num2 == "0":
        return "0"

    # Line 2: Initialize result array
    n1, n2 = len(num1), len(num2)
    result = [0] * (n1 + n2)

    # Line 3: Multiply digits right-to-left
    for i in range(n1 - 1, -1, -1):
        for j in range(n2 - 1, -1, -1):
            # Line 4: Convert digits to integers
            digit1 = ord(num1[i]) - ord('0')
            digit2 = ord(num2[j]) - ord('0')
            # Line 5: Current product
            temp = digit1 * digit2 + result[i + j + 1]
            # Line 6: Update digits and carry
            result[i + j + 1] = temp % 10
            result[i + j] += temp // 10

    # Line 7: Build result string
    start = 0
    while start < len(result) and result[start] == 0:
        start += 1
    if start == len(result):
        return "0"

    # Line 8: Convert to string
    return ''.join(map(str, result[start:]))

Alternative: Array Multiplication Approach

Explanation

Multiply each digit of num2 with all of num1, storing intermediate results in arrays, then sum them with proper alignment. Similar to manual multiplication but more verbose.

Multiply Each Digit.
Align and Sum.
Build String.

Step-by-Step Example (Alternative)

For "123" * "456":

Start: intermediates = [].
Step 1: 123 * 6 = "738", intermediates = ["738"].
Step 2: 123 * 5 = "615", align with 0, intermediates = ["738", "6150"].
Step 3: 123 * 4 = "492", align with 00, intermediates = ["738", "6150", "49200"].
Step 4: Sum: 738 + 6150 + 49200 = 56088.
Finish: Return "56088".

How the Code Works (Array Multiplication)

def multiplyArray(num1: str, num2: str) -> str:
    # Line 1: Handle zero
    if num1 == "0" or num2 == "0":
        return "0"

    # Line 2: Store intermediate results
    intermediates = []
    for j in range(len(num2) - 1, -1, -1):
        carry = 0
        temp = ""
        # Line 3: Multiply num1 by digit of num2
        for i in range(len(num1) - 1, -1, -1):
            prod = (ord(num1[i]) - ord('0')) * (ord(num2[j]) - ord('0')) + carry
            temp = str(prod % 10) + temp
            carry = prod // 10
        if carry:
            temp = str(carry) + temp
        # Line 4: Add trailing zeros
        temp += "0" * (len(num2) - 1 - j)
        intermediates.append(temp)

    # Line 5: Sum intermediates
    result = "0"
    for num in intermediates:
        carry = 0
        temp = ""
        i, j = len(result) - 1, len(num) - 1
        while i >= 0 or j >= 0 or carry:
            x = ord(result[i]) - ord('0') if i >= 0 else 0
            y = ord(num[j]) - ord('0') if j >= 0 else 0
            total = x + y + carry
            temp = str(total % 10) + temp
            carry = total // 10
            i -= 1
            j -= 1
        result = temp

    # Line 6: Return result
    return result

Complexity

Digit-by-Digit:

Time: O(n1 * n2) – Multiply each pair of digits.
Space: O(n1 + n2) – Result array.

Array Multiplication:

Time: O(n1 * n2 + k) – k is sum of intermediate lengths.
Space: O(n1 * n2) – Intermediate strings.

Efficiency Notes

Digit-by-Digit is O(n1 * n2) time and O(n1 + n2) space, optimal for LeetCode 43. Array Multiplication is less efficient in space due to storing intermediates but mimics manual steps.

Key Insights

Tips to master LeetCode 43:

Position Matters: i+j+1 for units, i+j for carry.
Carry Handling: Propagate carries digit-by-digit.
No Conversion: Work with strings directly.

Additional Example

For num1 = "99", num2 = "9":

Goal: "891".
Digit-by-Digit: result = [0,8,9,1], return "891".
Result: "891".

Edge Cases

Zeros: "0" * "123" – Return "0".
Single Digit: "5" * "6" – Return "30".
Large Numbers: "12345" * "6789" – Handle big products.

Final Thoughts

The Digit-by-Digit solution is a clean win for LeetCode 43 in Python—efficient, straightforward, and true to string manipulation. For a related challenge, try LeetCode 42: Trapping Rain Water to switch gears with arrays! Ready to multiply? Solve LeetCode 43 on LeetCode now and test it with "123456" or "9999" to master big-number multiplication. Dive in and crunch those digits!