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


  • 0
    R

    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'
            }

Log in to reply
 

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