a strobogrammatic number is a number that looks the same when rotated 180 degrees looked at upside down find all strobogrammatic numbers that are of length n for example given n 2 return 11 69 88 96 given n generate all strobogrammatic numbers of length n type n int rtype liststr type low str type high str rtype int given n generate all strobogrammatic numbers of length n type n int rtype list str type low str type high str rtype int
def gen_strobogrammatic(n):
    
    return helper(n, n)

def helper(n, length):
    if n == 0:
        return [""]
    if n == 1:
        return ["1", "0", "8"]
    middles = helper(n-2, length)
    result = []
    for middle in middles:
        if n != length:
            result.append("0" + middle + "0")
        result.append("8" + middle + "8")
        result.append("1" + middle + "1")
        result.append("9" + middle + "6")
        result.append("6" + middle + "9")
    return result

def strobogrammatic_in_range(low, high):
    
    res = []
    count = 0
    low_len = len(low)
    high_len = len(high)
    for i in range(low_len, high_len + 1):
        res.extend(helper2(i, i))
    for perm in res:
        if len(perm) == low_len and int(perm) < int(low):
            continue
        if len(perm) == high_len and int(perm) > int(high):
            continue
        count += 1
    return count

def helper2(n, length):
    if n == 0:
        return [""]
    if n == 1:
        return ["0", "8", "1"]
    mids = helper(n-2, length)
    res = []
    for mid in mids:
        if n != length:
            res.append("0"+mid+"0")
        res.append("1"+mid+"1")
        res.append("6"+mid+"9")
        res.append("9"+mid+"6")
        res.append("8"+mid+"8")
    return res