Python solution 180ms


  • 9
    Y

    The solution is also base on strobogrammatic number II, but with a little optimization.

    class Solution:
    # @param {string} low
    # @param {string} high
    # @return {integer}
    def strobogrammaticInRange(self, low, high):
        a=self.below(high)
        b=self.below(low,include=False)
        return a-b if a>b else 0
    
    '''
    get how many strobogrammatic numbers less than n
    '''
    def below(self,n,include=True):
        res=0
        for i in range(1,len(n)):
            res+=self.number(i)
        l=self.strobogrammatic(len(n))
        '''
        filter num larger than n and start with 0
        '''
        if include:
            l=[num for num in l if (len(num)==1 or num[0]!='0') and num<=n]
        else:
            l=[num for num in l if (len(num)==1 or num[0]!='0') and num<n]
        return res+len(l)
    
    '''
    get strobogrammatic numbers with length l
    number start with 0 would be included
    '''
    def strobogrammatic(self,l):
        res=[]
        if l==1:
            return ['0','1','8']
        if l==2:
            return ['00','11','69','96','88']
        for s in self.strobogrammatic(l-2):
            res.append('0'+s+'0')
            res.append('1'+s+'1')
            res.append('6'+s+'9')
            res.append('8'+s+'8')
            res.append('9'+s+'6')
        return res
    
    '''
    get number of strobogrammatic numbers of length l
    '''
    def number(self,l):
        if l==0:
            return 0
        '''
        If l is an even number, the first digit has four choices (1,6,8,9). digits 
        at other position have five choices(0,1,6,8,9)
        '''
        if l%2==0:
            return 4*(5**(l/2-1))
        '''
        If l is an odd number, the first digit has four choices (1,6,8,9) and digit 
        at the middle has 3 choices (0,1,8),other digits have 5 choices.
        digit at other position could be 0,1,6,8,9
        '''
        elif l==1:
            return 3
        else:
            return 3*(5**(l/2-1))*4

  • 0

    Hi, yang.zheng.904. Could you please give some explanations for your function number?


  • 0
    Y

    Hi, jianchao, I have added explanations to that function.


  • 0

    Hi, yang.zheng.904. Thank you for your nice explanations :-) I get it now.

    BTW, translating this code into C++ directly gives the MLE...


  • 1
    C

    Nice solution and nice explanation, a little bit change to your solution:

    def strobogrammaticInRange(self, low, high):
        a, b = self.below(high), self.below(low, include=False) 
        return a -b if a > b else 0
        
    def below(self, n, include=True):
        res = 0
        for i in xrange(1, len(n)):
            res += self.number(i)
        l = self.strobogrammatic(len(n))
        if include:
            tmp = [num for num in l if num <= n]
        else:
            tmp = [num for num in l if num < n]
        return res + len(tmp)
        
    def strobogrammatic(self, n):
        return self.helper(n, n)
        
    def helper(self, m, n):
        if m == 0:
            return [""]
        if m == 1:
            return ["0", "1", "8"]
        l = self.helper(m-2, n)
        res = []
        for i in l:
            if m != n:
                res.append("0"+i+"0")
            res.append("1"+i+"1")
            res.append("6"+i+"9")
            res.append("8"+i+"8")
            res.append("9"+i+"6")
        return res
        
    def number(self, l):
        if l == 0:
            return 0
        if l % 2 == 0:
            return 4*(5**(l/2-1))
        elif l == 1:
            return 3
        else:
            return 3*(5**(l/2-1))*4

  • 0
    F

    Great combination of recursive and math! That's brilliant!


  • 0
    T

    @caikehe

    The code for generating res could be shorten like this

    return [a + i + b for a, b in ['00', '11', '69', '88', '96'][m == n:] for i in l]
    

Log in to reply
 

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