• ㊗️
• 大家
• offer
• 多多！

## Problem

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


## Code

class Solution {
public List<String> findStrobogrammatic(int n) {
HashMap<String, String> map = new HashMap<>();
map.put("0", "0");
map.put("1", "1");
map.put("6", "9");
map.put("8", "8");
map.put("9", "6");

List<String> res = new ArrayList<>();
String curr = "";
if(n % 2 == 1) {
helper(res, "0", map, n - 1);
helper(res, "8", map, n - 1);
helper(res, "1", map, n - 1);
} else {
helper(res, "", map, n);
}
return res;
}

private void helper(
List<String> res,
String curr,
HashMap<String, String> map,
int remain) {

if(remain == 0) {
return;
}

for(String key : map.keySet()) {
if(remain == 2 && key == "0") continue;
helper(res, key + curr + map.get(key), map, remain - 2);
}
}
}

class Solution:
def findStrobogrammatic(self, n: int) -> List[str]:
map = {
"0": "0",
"1": "1",
"6": "9",
"8": "8",
"9": "6",
}

res = []

if n % 2 == 1:
res = ["0", "1", "8"]
n -= 1
else:
res = [""]

while n != 0:
size = len(res)
while size != 0:
size -= 1
r = res.pop(0)
for key in map:
if n == 2 and key == "0":
continue
res.append(key + r + map[key])

n -= 2

return res