Leetcode 247. Strobogrammatic Number II

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.

Example:

Input:  n = 2
Output: ["11","69","88","96"]

Difficulty: Medium

Solution:

class Solution:
    """
    @param n: the length of strobogrammatic number
    @return: All strobogrammatic numbers
    """
    def findStrobogrammatic(self, n):
        def dfs(i, center, left, right):
            if i == (n + 1) // 2:
                res.append(left + center + right)
                return
            if n % 2 == 1 and i == 0:
                for c in center_candidate:
                    dfs(i + 1, c, left, right)
            else:
                for k in m:
                    if i == (n + 1) // 2 - 1 and k == '0':
                        continue
                    dfs(i + 1, center, k + left, right + m[k])
                
        if n == 0:
            return ['']
        m = {'0': '0', '1': '1', '6': '9', '8': '8', '9': '6'}
        center_candidate = ('0', '1', '8')
        res = []
        dfs(0, '', '', '')
        return res