Fast general solution with detailed solution without generating numbers


  • 2

    1. Introduction

    The idea based on this post. I rewrote some part of the codes and made it more general and understandable to all the language coding member. The main idea is as follow:

    1. count the number less than high.
    2. count the number less than low-1.
    3. minus the two result getting the final answer.

    2. Count the strobogrammatic number less than a number

    We can divide the problem into two mini issues.

    1. Count the number with the less length than the target string number.
    2. Count the number with the same length of the target string number.

    2.1 With less length

    To solve this problem, we can use dynamic programming. We know the following transfer equation:
    dp[0]=1 dp[1]=3,dp[2]=5 dp[i]=dp[i-2]*5
    It's simple to get the results. However, the results contain the first digital with 0. To get rid of these invalid results, we only need times4/5 since the are 5 in dp[2].

    2.2 With the same length

    It's the core and hard part of this problem. We need to take consideration of the total length and the situation equal to the target number.
    Using one pointer spos to locate the candidate numbers and another length iteration pointer pstr. Every iteration the total length minus 2 since we get rid of the fist and last characters. For the candidates, there are three situations:

    • Only one digital, it's (0,1,8)
    • The first layer means the first pair, it's could be (1,6,8,9)
    • The others could be (0, 1, 6, 8, 9)

    For all the numbers in candidates,

    1. if the number less than the target position number, we can directly add the dp[pstr-2].
    2. If it equals, we need to do more work. Checking the mapping position number is less than or equal to the target, record the count of this situations. If only reaches the half length of the numbers, it could be the right candidates. For example: the target number is 8 9 7 8 9, the fist candidate number is 8 and the second is 9, since the 8<9 and '6<8' , we reaches the most inner layer of the number, so 8 9 * 6 8 is the candidates (* means less than 7).

    The coding could be like this:

    class Solution(object):
        def __init__(self):
            # 1-{0,1,8} 2-{00,11,69,88,96}
            self.cntmemo = {-1: 1, 0: 1, 1: 3, 2: 5}
            # mapping the corresponding number
            self.mapping = {0: 0, 1: 1, 6: 9, 8: 8, 9: 6}
    
        def count_same_len(self, str_num):
            slen = len(str_num)
            spos, pstr = 0, slen
            rescnt = 0
            # record equal cnt when compare with the target
            lesscnt = 0
            while pstr > 0:
                if slen == 1 or pstr == 1:
                    candidates = (0, 1, 8)
                # first digital get rid of 0
                elif pstr == slen:
                    candidates = (1, 6, 8, 9)
                else:
                    candidates = (0, 1, 6, 8, 9)
                for num in candidates:
                    # if the number less than the target,add all the possible in strlen-2
                    if num < int(str_num[spos]):
                        rescnt += self.cntmemo[pstr - 2]
                    # if equal we need to record, util to the middle compare
                    elif num == int(str_num[spos]):
                        # if the mapping pos num less or equal to the target, it's possible
                        if self.mapping[num] <= int(str_num[slen-1-spos]):
                            # record the less cnt
                            lesscnt += 1
                            if pstr < 3 and lesscnt == (slen + 1) / 2:
                                rescnt += 1
                        break
                    else:
                        return rescnt
                pstr -= 2
                spos += 1
            return rescnt
        
        def count_less_than(self, str_num):
            rescnt, slen = 0, len(str_num)
            # count the number less than str_num with length less than str len
            if int(str_num) < 0: return 0
            if slen > 1:
                # len==1
                rescnt = 3
                # len>2
                for i in xrange(2, slen):
                    rescnt += self.cntmemo[i] * 4 / 5
            # plus the number with the same length
            return rescnt+self.count_same_len(str_num)
    
        def strobogrammaticInRange(self, low, high):
            if int(low) > int(high):
                return 0
            # count all larger than 2
            for i in xrange(3, len(high)):
                self.cntmemo[i] = self.cntmemo[i - 2] * 5
            return self.count_less_than(high) - self.count_less_than(str(int(low)-1))
    

Log in to reply
 

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