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"]

Thoughts:

1. Recursion: T(n) = append each string with ("1", "1"); ("6","9"); ("9","6"); ("8","8"); if not at the out-most recursion; also add ("0","0") from returned element from T(n - 2); Base case: (n =0 => ['']; n = 1=>['0', '1', '8'])

2. Without Recursion: reverse the order with for loop

Code: Recursion

class Solution(object):
    def findStrobogrammatic(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        def helper(cur_len, total_len):
            # base case 
            if cur_len == 0: return ['']
            if cur_len == 1: return ['0', '1', '8']
            ans = []
            sub = helper(cur_len - 2, total_len)

            for s in sub:
                if cur_len != total_len:
                    ans.append("0" + s + "0")
                ans.append("1" + s + "1")
                ans.append("6" + s + "9")
                ans.append("8" + s + "8")
                ans.append("9" + s + "6")

            return ans

        return helper(n, n)

Code: Without Recursion

class Solution(object):
    def findStrobogrammatic(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        one , two = ['0','1', '8'] , [''] # two base case
        ans = one if n % 2 == 1 else two

        i = n % 2 + 2
        while(i <= n):
            new = []
            for s in ans:
                if i != n: 
                    new.append("0" + s + "0")
                new.append("1" + s + "1")
                new.append("6" + s + "9")
                new.append("8" + s + "8")
                new.append("9" + s + "6")
            ans = new
            i += 2

        return ans