Multiply Strings
Problem Statement
You are given two strings num1
and num2
that represent non-negative integers.
Return the product of num1
and num2
in the form of a string.
Assume that neither num1
nor num2
contain any leading zero, unless they are the number 0
itself.
Note: You can not use any built-in library to convert the inputs directly into integers.
Example 1:
Input: num1 = "3", num2 = "4"
Output: "12"
Example 2:
Input: num1 = "111", num2 = "222"
Output: "24642"
Constraints:
1 <= num1.length, num2.length <= 200
num1
andnum2
consist of digits only.
Recommended Time and Space Complexity
You should aim for a solution with O(m * n) time and O(m + n) space, where m and n are the lengths of the input strings.
Hint 1
Consider the elementary school method of multiplication. How can you simulate this process with strings?
Hint 2
Each digit in num1
must be multiplied by each digit in num2
.
Hint 3
Think about how to manage carries when multiplying and adding the intermediate products.
Solution
Multiplication & Addition
def multiply(num1: str, num2: str) -> str: if num1 == "0" or num2 == "0": return "0"
if len(num1) < len(num2): return multiply(num2, num1)
res, zero = "", 0 for i in range(len(num2) - 1, -1, -1): cur = _mul(num1, num2[i], zero) res = _add(res, cur) zero += 1
return res
def _mul(s: str, d: str, zero: int) -> str: i, carry = len(s) - 1, 0 d = int(d) cur = []
while i >= 0 or carry: n = int(s[i]) if i >= 0 else 0 prod = n * d + carry cur.append(str(prod % 10)) carry = prod // 10 i -= 1
return ''.join(cur[::-1]) + '0' * zero
def _add(num1: str, num2: str) -> str: i, j, carry = len(num1) - 1, len(num2) - 1, 0 res = []
while i >= 0 or j >= 0 or carry: n1 = int(num1[i]) if i >= 0 else 0 n2 = int(num2[j]) if j >= 0 else 0 total = n1 + n2 + carry res.append(str(total % 10)) carry = total // 10 i -= 1 j -= 1
return ''.join(res[::-1])
Time complexity: O(min(m, n) * (m + n)) Space complexity: O(m + n)
Where m is the length of the string num1 and n is the length of the string num2.