Problem statement

https://binarysearch.com/problems/Upside-Down-Numbers/

Solution

Equal to Leetcode 0247. Strobogrammatic Number II.

Complexity

Time and space complexity is O(5^n*n), number of possible numbers.

Code

class Solution:
    def solve(self, n):
        d = {"0":"0", "1":"1", "6":"9", "8":"8", "9":"6"}
        
        def dfs(n):
            if n == 0: return [""]
            if n == 1: return ["0", "1", "8"]
            ans = []
            found = dfs(n - 2)
            for dig in d:
                for s in found:
                    ans.append(dig + s + d[dig])
            
            return ans
        
        if n == 0: return []
        return [i for i in dfs(n) if (i[0] != "0" or i == "0")]