Problem statement

https://binarysearch.com/problems/String-Multiplication/

Solution

Equal to Leetcode 0043. Multiply Strings, but process negative numbers.

Complexity

It is O(mn) for time and O(m + n) for space.

Code

class Solution:
    def solve(self, num1, num2):
        sgn = "-" if (num1 + num2).count("-") == 1 else ""
        if num1[0] == "-": num1 = num1[1:]
        if num2[0] == "-": num2 = num2[1:]
        m, n = len(num1), len(num2)
        d = Counter()
        for i in range(m):
            for j in range(n):
                d[i+j] += int(num1[m-1-i])*int(num2[n-1-j])
                
        carry, ans = 0, ""
        for i in range(m+n-1):
            carry, digit = divmod(carry + d[i], 10)
            ans += str(digit)
            
        ans = (str(carry) + ans[::-1]).lstrip("0")
        return sgn + ans if ans != "" else "0"