Leetcode 247. Strobogrammatic Number II

[locked]
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.

---

Using DFS. All 5 numbers can be used for each half position except the single position(6 and 9 can not be used while there is only one position), and the other half are decided in this way. So we have nearly 5^(n/2) such numbers!

# Time:  O(n^2 * 5^(n/2))
# Space: O(n)

class Solution:
    lookup = {'0':'0', '1':'1', '6':'9', '8':'8', '9':'6'}

    # @param {integer} n
    # @return {string[]}
    def findStrobogrammatic(self, n):
        return self.findStrobogrammaticRecu(n, n)

    def findStrobogrammaticRecu(self, n, k):
        if k == 0:
            return ['']
        elif k == 1:
            return ['0', '1', '8']
        
        result = []
        for num in self.findStrobogrammaticRecu(n, k - 2):
            for key, val in self.lookup.iteritems():
                if n != k or key != '0':
                    result.append(key + num + val)

        return result