Multiply Strings Leetcode Problem 43 [Python Solution]

In this blog post, we will delve into the LeetCode problem Multiply Strings This problem involves multiplying two non-negative integers represented as strings and returning the product as a string.

The challenge here is to perform this multiplication without using any built-in BigInteger library or converting the inputs to integers directly.

We'll explore an efficient Python solution that accomplishes this task and understand the underlying algorithm and reasoning behind it.

You can find the problem on LeetCode here.

Problem Overview

The problem statement can be summarized as follows:

Given two non-negative integers, num1 and num2, represented as strings, we need to find their product and return it as a string.

Example 1:

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

Output:
"6"

Example 2:

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

Output:
"56088"

Constraints:

The lengths of num1 and num2 are both between 1 and 200.
Both num1 and num2 consist of digits only.
Neither num1 nor num2 contains any leading zero, except for the number 0 itself.

To tackle this problem, we will first understand the constraints, edge cases, and then explore an efficient Python solution.

Understanding the Constraints

Before we dive into the solution, let's understand the constraints given in the problem:

The lengths of num1 and num2 are between 1 and 200. This means that the input strings can be quite long, so our solution should be efficient.
Both num1 and num2 consist of digits only, which ensures that we don't need to handle non-numeric characters in the input.
Neither num1 nor num2 contains any leading zeros, except for the number 0 itself.

This is an important detail to consider when multiplying and when converting the result back to a string.

Edge Cases a Valid Solution Must Consider

Before proceeding with the solution, let's identify some edge cases that our solution should handle:

Zero as Input: If either num1 or num2 is "0," the result will be "0." This is because any number multiplied by zero is zero.

Our code should efficiently handle this case and return "0."

Output Length: As the problem allows for very long inputs, the resulting product could have more digits than the sum of the digits in the input numbers.

For example, multiplying "99" by "99" yields "9801," a four-digit product.

We need to ensure that leading zeros are not included in the result, and the length of the output is correctly calculated.

Now, let's explore an efficient approach to solving the Multiply Strings problem.

Efficient Python Code Solution

We'll implement an efficient Python solution to multiply two strings, considering the constraints and edge cases.

The basic idea is to perform the multiplication manually, similar to the long multiplication method we learned in elementary school.

Here's the Python code solution:

View on GitHub ➹

def multiply(num1: str, num2: str) -&gt; str:
    # Check if either input is &quot;0,&quot; in which case the result is also &quot;0.&quot;
    if &quot;0&quot; in [num1, num2]:
        return &quot;0&quot;

    # Initialize a result array with zeros to store the product.

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

    # Reverse the input strings for convenient processing.

num1, num2 = num1[::-1], num2[::-1]

    # Perform the multiplication digit by digit.

for i1 in range(len(num1)):
        for i2 in range(len(num2):
            # Calculate the product of the digits and add it to the appropriate position in the result.

digit = int(num1[i1]) * int(num2[i2])
            result[i1 + i2] += digit

            # Handle any carry to the next position.

result[i1 + i2 + 1] += result[i1 + i2] // 10
            result[i1 + i2] = result[i1 + i2] % 10

    # Reverse the result array and find the position without leading zeros.

result, beg = result[::-1], 0
    while beg &lt; len(result) and result[beg] == 0:
        beg += 1

    # Convert the result to a string and return it.

result = map(str, result[beg:])
    return &quot;&quot;.join(result)

This solution efficiently handles the multiplication of two strings, considering edge cases and constraints.

1. Bruteforce Approach:

The bruteforce approach involves simulating manual multiplication step by step, similar to the long multiplication method taught in elementary school.

It iterates through the digits of both input strings and performs the necessary calculations to obtain the product.

The critical steps include multiplying individual digits, keeping track of carry values, and placing digits in the correct positions.


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

for i1 in range(len(num1)):
    for i2 in range(len(num2):
        # Calculate the product of the digits
        digit = int(num1[i1]) * int(num2[i2])
        
        # Add the product to the appropriate position in the result
        result[i1 + i2] += digit
        
        # Handle carry values
        result[i1 + i2 + 1] += result[i1 + i2] // 10
        result[i1 + i2] = result[i1 + i2] % 10

2. Efficient Approach:

The efficient approach eliminates the need for nested loops by pre-allocating an array for the result, which makes the code more concise and efficient.

It maintains the same principles as the bruteforce approach, such as multiplying digits, handling carries, and placing digits in the correct positions.

In this approach, we use reversed input strings for easier processing and utilize an array for the result.

The multiplication is performed without explicit nested loops, and carry values are managed efficiently.


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

num1, num2 = num1[::-1], num2[::-1]

for i1 in range(len(num1)):
    for i2 in range(len(num2):
        # Calculate the product of the digits
        digit = int(num1[i1]) * int(num2[i2])
        
        # Add the product to the appropriate position in the result
        result[i1 + i2] += digit
        
        # Handle carry values
        result[i1 + i2 + 1] += result[i1 + i2] // 10
        result[i1 + i2] = result[i1 + i2] % 10


result,

 beg = result[::-1], 0
while beg < len(result) and result[beg] == 0:
    beg += 1


result = map(str, result[beg:])
return "".join(result)

This efficient approach simplifies the code and makes it more readable while maintaining the correct algorithm.

Time and Space Complexity

Let's analyze the time and space complexity of our efficient Python solution:

Time Complexity: The time complexity is determined by the two nested loops iterating through the input strings, resulting in a time complexity of O(n * m), where n is the length of num1, and m is the length of num2.
Space Complexity: The space complexity is primarily determined by the result array, which has a size of O(n + m).

Additionally, we use some auxiliary variables, so the overall space complexity is O(n + m).

Reasoning Behind Our Approach

Our approach is based on the concept of manual multiplication, which is taught in elementary school.

We simulate this process step by step, considering the digits of the input numbers, carries, and correct placement of digits in the result.

Here's a breakdown of our reasoning:

Multiplying Digits: We start by multiplying the digits of num1 with the digits of num2, one pair at a time.

We calculate the product and add it to the appropriate position in the result array.

Carry Management: After each multiplication, we check if there is a carry, and if so, we add it to the next position in the result array.

This ensures that we correctly manage carry values as we would in manual multiplication.

Handling Leading Zeros: After the multiplication, we might have leading zeros in the result array.

We remove these leading zeros to ensure that the result is in the correct format.

Converting to String: The result is stored as an array of integers.

We convert it to a string before returning it as the final output.

This approach simplifies the multiplication process and is efficient in terms of time and space complexity.

Conclusion

In this blog post, we tackled the LeetCode problem Multiply Strings and provided an efficient Python solution.

We began by understanding the problem statement, constraints, and edge cases.

We discussed the bruteforce approach and introduced the efficient approach, which simplifies the code while maintaining correctness.

Multiplying two strings without converting them to integers is a common problem in programming interviews, and understanding the manual multiplication process is valuable.

Our solution handles this problem efficiently and provides a clear understanding of the underlying algorithm.

We encourage you to comment, ask questions, make suggestions, and share this content with others who might find it helpful.

By practicing such problems, you can enhance your problem-solving skills and become a better programmer.

If you'd like to try the code for yourself, you can find the problem on LeetCode here.