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]
    

  • 0
    B

    @tlhuang
    that is unreadable like hell.


  • 0
    B

    The math trick must be what interviewer is looking for (given you have implemented II).


Log in to reply
 

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