Python DP solution, can't believe beating 98%.


  • 0
    Y
    class Solution(object):
        def __init__(self):
            preRequisites = {1:{4:2,64:8,256:16},2:{128:16},
                             4:{1:2,64:16,256:32},8:{32:16},32:{8:16},
                             64:{1:8,4:16,256:128},128:{2:16},
                             256:{64:128,1:16,4:32}}
            digits2nums,num2count,self.digits2counts = {i:[] for i in xrange(1,10)},{(1<<i):{(1<<i):1} for i in xrange(9)},{1:9}
            for i in xrange(1,512):
                n,digits = i,0
                while n>0:
                    digits += 1
                    n -= n&(-n)
                digits2nums[digits].append(i)
            for digits in xrange(2,10):
                self.digits2counts[digits] = 0
                for num in digits2nums[digits]:
                    num2count[num],n = {},num
                    while n>0:
                        last = n&(-n)
                        preNum,num2count[num][last] = num^last,0
                        nn = preNum
                        while nn>0:
                            preLast = nn&(-nn)
                            if preLast in preRequisites and last in preRequisites[preLast]:
                                if preRequisites[preLast][last]&preNum>0:
                                    num2count[num][last] += num2count[preNum][preLast]
                            else:
                                num2count[num][last] += num2count[preNum][preLast]
                            nn -= preLast
                        self.digits2counts[digits] += num2count[num][last]
                        n -= last
            
            
        def numberOfPatterns(self, m, n):
            """
            :type m: int
            :type n: int
            :rtype: int
            """
            ans = 0
            for i in xrange(m,n+1):
                ans += self.digits2counts[i]
            return ans
    

    A little bit explanation:

    We can use numbers from 0 to 511 to represent which keys in a pattern have been passed. e.g. 111100111(487) means keys 1,2,3,6,7,8,9 have been passed.

    Another important thing is for each key, which one is the last key passed in this pattern. e.g. when we consider 111100111(487) with the last key to be 9, we have to consider 011100111(231) with the last key being 1,2,3,6,7,8 respectively. Among them if the last key of 231 is 1, then it's impossible because 5 has not been passed.

    Therefore in the DP table we record the number of patters corresponding to:

    1. The number representing which keys have been passed.
    2. The last passed key among those keys.

Log in to reply
 

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