Leetcode 0247. Strobogrammatic Number II

Problem statement

https://leetcode.com/problems/strobogrammatic-number-ii/

Solution

Let us just generate all numbers with recursion. If we have $0$ or $1$ digits, this is the base of our recursion. If we have $n$ digits, generate all numbers with $n-2$ digits and then add pairs of digits to the beginning and to the end. In the end remove all numbers which start with $0$.

Complexity

Time and space complexity is $\mathcal{O}(5^n\cdot n)$, number of possible numbers.

Code

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