Strobogrammatic Number II

Problem: Strobogrammatic Number II

The general idea is to add a pair of appropriate numbers at head and tail of current string result. Odd numbers are special situations and we can deal with it by passing in 0, 1, 8 at first recursion and minus n with 1. 0 is also a special number since it can not be added to the first digit of a non-zero number, which means we need to do some judge.

Code in Python:

class Solution(object):
    def findStrobogrammatic(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        pairs = [("1", "1"), ("6", "9"), ("8", "8"), ("9", "6")]
        ans = []

        def generate(n, s):
            if n == 0:
                ans.append(s)
                return
            if n != 2: generate(n-2, "0"+s+"0")
            for pair in pairs:
                generate(n-2, pair[0]+s+pair[1])

        if n % 2 == 0:
            generate(n, "")
        else:
            generate(n-1, "0")
            generate(n-1, "1")
            generate(n-1, "8")
        return ans