LC 43 - Multiply Strings

Question

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.

Links

Question here and solution here

Solution

concept

This question just have to follow what multiplication by hand does

code

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == "0" or num2 == "0":
            return "0"
        # preset a maximum possible answer arr
        ans = [0]*(len(num1) + len(num2))
        # reverse for easier calc
        num1, num2 = num1[::-1], num2[::-1]

        for i1 in range(len(num1)):
            for i2 in range(len(num2)):
                digit = int(num1[i1]) * int(num2[i2])
                # answer go to the correct index + whatever carry it is from the previous calc
                ans[i1 + i2] += digit # possible it is > 9, will handle later
                # carry to the next
                ans[i1 + i2 + 1] += (ans[i1 + i2] // 10)
                # handle > 9
                ans[i1 + i2] = ans[i1 + i2] % 10
        # handle leading zero after reversing ans
        ans, beg = ans[::-1], 0
        while beg < len(ans) and ans[beg] == 0:
            beg += 1
        # change back to str
        ans = map(str, ans[beg:])
        return "".join(ans)

Complexity

time: $O(mn)$
space: $O(m+n)$