generate_strobogrammtic.py

"""
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"].
"""


def gen_strobogrammatic(n):
    """
    :type n: int
    :rtype: List[str]
    """
    result = helper(n, n)
    return result


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 strobogrammaticInRange(low, high):
    """
    :type low: str
    :type high: str
    :rtype: int
    """
    res = []
    count = 0
    for i in range(len(low), len(high) + 1):
        res.extend(helper2(i, i))
    for perm in res:
        if len(perm) == len(low) and int(perm) < int(low):
            continue
        elif len(perm) == len(high) and int(perm) > int(high):
            continue
        else:
            count += 1
    return count


def helper2(self, 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