Multiply Strings - Leetcode Solution

Problem Statement:

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

Example 1:

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

Example 2:

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

Note:

The length of both num1 and num2 is < 110. Both num1 and num2 contain only digits 0-9. Both num1 and num2 do not contain any leading zero, except the number 0 itself. You must not use any built-in BigInteger library or convert the inputs to integer directly.

Solution:

One approach to solve the problem is to simulate the multiplication process we use in our school. The idea is to multiply each digit of the second number (i.e., num2) with each digit of the first number (i.e., num1) and add the results at the appropriate positions to get the final product. We can store the result in a list and then convert it to a string.

Algorithm:

1. Initialize a list res with length (m+n) and fill it with 0's where m and n are the length of num1 and num2 respectively.
2. Reverse both strings (num1 and num2) to start from the least significant digit.
3. Traverse num1 from right to left and multiply each digit with num2 from right to left. The product will have two digits, and we can keep the least significant digit at the current position and carry the higher digit to the next position.
4. After completing the first multiplication, we will have m+n-1 digits in the result. If there is a carry at the last position, add it to the next position.
5. Repeat the same process for all digits of num1.
6. Remove the leading zeros from the result, and if the result is empty, return "0".
7. Convert the result list to a string and return it.

Time Complexity: O(m*n), where m and n are the lengths of num1 and num2 respectively, as we need to multiply each digit of num1 with each digit of num2.

Space Complexity: O(m+n), for the result list.

Python Code:

class Solution: def multiply(self, num1: str, num2: str) -> str:

    m, n = len(num1), len(num2)
    res = [0]*(m+n)
    
    num1 = num1[::-1]
    num2 = num2[::-1]
    
    for i in range(m):
        carry = 0
        for j in range(n):
            prod = int(num1[i])*int(num2[j])
            pos = i+j
            res[pos] += (prod%10 + carry)
            carry = prod//10 + res[pos]//10
            res[pos] = res[pos]%10
            
        if carry:
            res[i+j+1] += carry
    
    while len(res)>1 and res[-1]==0:
        res.pop()
    
    return "".join(map(str, res[::-1])) if res else "0"

1