# Python solution with detailed explanation

• Solution with discussion https://discuss.leetcode.com/topic/77972/python-solution-with-detailed-explanation

Multiply Strings https://leetcode.com/problems/multiply-strings/

Brute Force Solution

• Multiple digit by digit and use add strings to form the answer. This results in TLE.
• We need to use addStrings since overflow can happen.
``````class Solution(object):
"""
:type num1: str
:type num2: str
:rtype: str
"""
N, M = len(num1), len(num2)
i,j = N-1, M-1
result, carry = [], 0
while i >= 0 or j >= 0:
if i >= 0 and j >= 0:
s = int(num1[i]) + int(num2[j]) + carry
s, carry = s%10, s//10
result.append(str(s))
i,j= i-1, j-1
elif i >= 0:
s = int(num1[i]) + carry
s, carry = s%10, s//10
result.append(str(s))
i= i-1
elif j >= 0:
s = int(num2[j]) + carry
s, carry = s%10, s//10
result.append(str(s))
j = j-1
if carry:
result.append(str(carry))
result.reverse()
return "".join(result)

def mult(self, s, digit):
factor, result, prev = 0, 0, "0"
for i in range(len(s)-1, -1, -1):
result = self.addStrings(str(int(digit)*int(s[i])) + "".join(["0"]*factor), prev)
prev = result
factor = factor + 1
return result

def multiply(self, num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
factor, result, prev = 0, 0, "0"
for i in range(len(num1)-1, -1, -1):
result = self.addStrings(self.mult(num2, num1[i]) + "".join(["0"]*factor), prev)
prev = result
factor = factor + 1
res = result.lstrip("0")
return "0" if not res else res
``````

Optimized Solution

• Fist determine how many digits in final answer. 99999 will have at max 5 digits. For n1 and n2, max size is len(n1)+len(n2).
• How do we multiply numbers using hand? We want a method by which we can directly update the result incrementally. Here is an an example: https://discuss.leetcode.com/topic/30508/easiest-java-solution-with-graph-explanation
• Reverse the inputs. The index in the reversed input should help you in determining the index of the resultant product.
• Given 2 digits, the result be atmost 2 digits. The result LSD will be placed at index i+j. MSD will be placed i+j+1. Now there could be a previous value at index i+j - that needs to be added to the product of two digits. Then we have to update indices i+j and i+j+1. Note there will be no carry generated at index i+j+1 since the maximum product can only be 81 and 8+1 =9
• Remove the unwanted zeroes. For that, try an example and be careful how we remove the zeroes.
• Here is a picture which shows the algorithm: https://goo.gl/photos/E3QyKGgUjpKJFRRRA
``````class Solution(object):
def multiply(self, num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
result = [0]*(len(num1) + len(num2))
for i,x in enumerate(reversed(num1)):
for j,y in enumerate(reversed(num2)):
a = int(x)*int(y) + result[i+j]
result[i+j] = int(a%10)
result[i+j+1] = result[i+j+1] + int(a/10)
last = 0
for i in range(len(result)-1, -1, -1):
if result[i] != 0:
last = i
break