Multiply Strings

Patrick Leaton
Published: March 23, 2021, 8:42 p.m.
Problem Description

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

 

Example 1:

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

Example 2:

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

 

Constraints:

  • 1 <= num1.length, num2.length <= 200
  • num1 and num2 consist of digits only.
  • Both num1 and num2 do not contain any leading zero, except the number 0 itself.

 

The description was taken from https://leetcode.com/problems/multiply-strings/.

Problem Solution

#O(N*M) Time, O(N) Space for Array
class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        product = [0] * (len(num1) + len(num2))
        for i in range(len(num1) -1, -1, -1):
            for j in range(len(num2)-1, -1, -1):
                num_one = ord(num1[i]) - ord('0')
                num_two = ord(num2[j]) - ord('0')
                value = (num_one * num_two) + product[i + j + 1]
                product[i+j+1] = value % 10
                product[i+j] += value //10
               
        pointer = 0
        while pointer < len(product)-1 and product[pointer] == 0:
            pointer += 1
        return ''.join(map(str, product[pointer:]))

Problem Explanation

We can solve this question as if we were multiplying these two numbers on paper, by traversing both strings moving from the least significant digit to the most, and at each index, we will place the product value under ten within the least most significant digits place within the output and carry the rest to the next iteration. 

This is similar to the previous variations of this problem with addition.

 

Kids Math: Long Multiplication

Let's initialize our product array which we will be returning to the combined length of both strings.  This is the maximum length the output could be.

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

 

Next, we will create a double loop moving from right to left to mimic the process of multiplying the bottom number in the one's place by the top number in the one's place, the tens place, the hundreds, etc., before then multiplying the bottom number in the tens place with the top number in the one's place, the tens place, the hundreds, etc.

        for i in range(len(num1) -1, -1, -1):
            for j in range(len(num2)-1, -1, -1):

 

Before we can actually multiply any numbers, we need to first convert them to integers. 

The problem description says we can't convert the numbers to integers directly.  This may have been referring to multiplying the entirety of the string and not each individual number, but regardless let's play on the safer side and use the numbers' order in the ASCII table to indirectly give us their integer values.

                num_one = ord(num1[i]) - ord('0')
                num_two = ord(num2[j]) - ord('0')
 

If we have nine, for example, its ASCII value is fifty-seven.  Zero's ASCII value is forty-eight.  If we subtract fifty-seven by forty-eight, we get nine, which is the integer we need.  The ASCII values aren't important to memorize, this is just how the ord function works for indirectly converting numbers to integers, or letters to integers as well.

 

During each iteration, we will calculate the product of the two numbers in question by using the process mentioned in the previous step.

However, we will also be adding the value in the index we saved within the output array from the previous iteration.

We do this to handle any values that need to be carried over.

                value = (num_one * num_two) + product[i + j + 1]

 

We'll then grab the least significant digit of the previous index so that we can carry over the rest to the current index. That way, if the value we just saved to the product array is greater than ten, it will be carried over within the next iteration.  

                product[i+j+1] = value % 10
                product[i+j] += value //10

 

Once we have the two input values multiplied and stored within our output array, we will want to remove any leading zeros before converting them to a string.

Let's use a pointer that will traverse the string until it stops on a character that isn't a zero.

        pointer = 0
        while pointer < len(product)-1 and product[pointer] == 0:
            pointer += 1

 

Afterward, we will know where our non-zero elements start.

Let's map the numbers to a string starting from the pointer to exclude any leading zeroes. 

We will then join the map object as a string and return it.  The mapping saves us from iterating through the string to convert the elements into strings.

        return ''.join(map(str, product[pointer:]))