You are given two non-negative integers num1 and num2 written as strings. Return their product, also as a string. You may not convert the inputs to built-in big integers or to numbers directly, because they can be far too long.
- 1 <= num1.length, num2.length <= 200
- Both contain only digits
- Neither has leading zeros, except the number "0" itself
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Converting to an integer fails once the strings are longer than about 18 digits. A first idea is to multiply num1 by each digit of num2 and add the shifted strings, which works but involves many string additions. The cleaner insight: a product of m and n digits has at most m + n digits, and digit i times digit j (counted from the left) always contributes to position i + j + 1 of the result. So we accumulate every pair product straight into an integer array, handling the carry as we go, then strip leading zeros.
Algorithm
- Create
resof sizem + n, filled with 0. - Loop
ifromm - 1down to 0 andjfromn - 1down to 0. - Compute
sum = d1 * d2 + res[i + j + 1]. Setres[i + j + 1] = sum % 10and addsum / 10tores[i + j]. - Skip leading zeros in
resand join the rest into a string. If nothing is left, return "0".
O(m * n)Space: O(m + n)class Solution: def multiply(self, num1: str, num2: str) -> str: m, n = len(num1), len(num2) res = [0] * (m + n) for i in range(m - 1, -1, -1): d1 = ord(num1[i]) - 48 for j in range(n - 1, -1, -1): d2 = ord(num2[j]) - 48 total = d1 * d2 + res[i + j + 1] res[i + j + 1] = total % 10 # digit stays here res[i + j] += total // 10 # carry moves left # skip leading zeros k = 0 while k < len(res) - 1 and res[k] == 0: k += 1 return "".join(str(d) for d in res[k:])