# Python: Use dict to minimize the use of internal sum and product ; easy to extend to other bases

• When I took this question, I assumed we were not allowed to use internal sum and product, like 3 + 3 and 3*3, so I decided to build the sum table and product table by use of dict in python. Here is the code (I hope it is not hard to understand)

``````class Solution(object):
def multiply(self, num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
M = {
'00':'00','01':'00','02':'00','03':'00','04':'00','05':'00','06':'00','07':'00','08':'00','09':'00',
'10':'00','11':'01','12':'02','13':'03','14':'04','15':'05','16':'06','17':'07','18':'08','19':'09',
'20':'00','21':'02','22':'04','23':'06','24':'08','25':'10','26':'12','27':'14','28':'16','29':'18',
'30':'00','31':'03','32':'06','33':'09','34':'12','35':'15','36':'18','37':'21','38':'24','39':'27',
'40':'00','41':'04','42':'08','43':'12','44':'16','45':'20','46':'24','47':'28','48':'32','49':'36',
'50':'00','51':'05','52':'10','53':'15','54':'20','55':'25','56':'30','57':'35','58':'40','59':'45',
'60':'00','61':'06','62':'12','63':'18','64':'24','65':'30','66':'36','67':'42','68':'48','69':'54',
'70':'00','71':'07','72':'14','73':'21','74':'28','75':'35','76':'42','77':'49','78':'56','79':'63',
'80':'00','81':'08','82':'16','83':'24','84':'32','85':'40','86':'48','87':'56','88':'64','89':'72',
'90':'00','91':'09','92':'18','93':'27','94':'36','95':'45','96':'54','97':'63','98':'72','99':'81'
}
S = {
'00':'0','01':'1','02':'2','03':'3','04':'4','05':'5','06':'6','07':'7','08':'8','09':'9',
'10':'1','11':'2','12':'3','13':'4','14':'5','15':'6','16':'7','17':'8','18':'9','19':'10',
'20':'2','21':'3','22':'4','23':'5','24':'6','25':'7','26':'8','27':'9','28':'10','29':'11',
'30':'3','31':'4','32':'5','33':'6','34':'7','35':'8','36':'9','37':'10','38':'11','39':'12',
'40':'4','41':'5','42':'6','43':'7','44':'8','45':'9','46':'10','47':'11','48':'12','49':'13',
'50':'5','51':'6','52':'7','53':'8','54':'9','55':'10','56':'11','57':'12','58':'13','59':'14',
'60':'6','61':'7','62':'8','63':'9','64':'10','65':'11','66':'12','67':'13','68':'14','69':'15',
'70':'7','71':'8','72':'9','73':'10','74':'11','75':'12','76':'13','77':'14','78':'15','79':'16',
'80':'8','81':'9','82':'10','83':'11','84':'12','85':'13','86':'14','87':'15','88':'16','89':'17',
'90':'9','91':'10','92':'11','93':'12','94':'13','95':'14','96':'15','97':'16','98':'17','99':'18'
}
if num1 == '0' or num2 == '0':
return '0'
#reverse the string
s1 = num1[::-1]
s2 = num2[::-1]
Mult = [[] for _ in range(len(s1)+len(s2))]
for i1 in range(len(s1)):
for i2 in range(len(s2)):
Mtmp = M[s1[i1]+s2[i2]]
Mult[i1+i2+1].append(Mtmp[0])
Mult[i1+i2].append(Mtmp[1])
for i in range(len(Mult)):
if Mult[i]==[]:
break
Snum = '0'
for j in Mult[i]:
Snum = S[Snum+j]
if len(Snum)>1:
Snum = Snum[1]
Mult[i+1].append('1')
Mult[i] = Snum
while Mult[-1] == ([] or '0'):
Mult.pop()
return ''.join(Mult[::-1])
``````

It is accepted and not so slow.

Since it does not use "+" and "*", so it is easy to extend to other bases. For example, to do the multiplication of binary strings, the only change is the M and S dict:

``````M = {
'00':'00','01':'00',
'10':'00','11':'01'
}
S = {
'00':'0','01':'1',
'10':'1','11':'10'
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.