[LeetCode] 043. Multiply Strings
-
date_range April 04, 2019 - Thursday info
Problem (Medium)
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.
Approach 1: (My Solution)
Idea
- Make two dictionaries:
-
- Adding dict (i.e. (‘1’, ‘1’): 2, (‘4’, ‘5’): 9, …);
-
- Multiplying dict (i.e. (‘0’, ‘8’): 0, (‘6’, ‘7’): 42, …);
-
- Follow the rules when we do multiplication by hand, when using simple adding or multiplying, check the dictionaries above.
Solution
class Solution1:
def multiply(self, num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
# Adding, multiplication dictionaries:
add = {tuple(sorted([str(i), str(j)])):i+j for i in range(10) for j in range(10)}
multi = {tuple(sorted([str(i), str(j)])):i*j for i in range(10) for j in range(10)}
# get trailing zeros in both numbers
if any((num1 == '0', num2 == '0')):
return '0'
zeros = ''
zeros += '0' * (len(num1) - len(num1.rstrip('0')))
zeros += '0' * (len(num2) - len(num2.rstrip('0')))
# Do the multiplication
res, num1, num2 = 0, num1.rstrip('0'), num2.rstrip('0')
for i, b in enumerate(num2[::-1]):
tmp, inc = 0, 0
for j, a in enumerate(num1[::-1]):
tmp += pow(10, j) * (multi[tuple(sorted([a, b]))] % 10 + inc)
inc = multi[tuple(sorted([a, b]))] // 10
if inc:
tmp += pow(10, len(num1)) * inc
res += pow(10, i) * tmp
return str(res) + zeros
Complexity
- Time: $O(mn)$
- Space: $O()$?
KF