## 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
``````