# Question

Formatted question description: https://leetcode.ca/all/247.html

Given an integer n, return all the strobogrammatic numbers that are of length n. You may return the answer in any order.

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Example 1:

Input: n = 2
Output: ["11","69","88","96"]


Example 2:

Input: n = 1
Output: ["0","1","8"]


Constraints:

• 1 <= n <= 14

# Algorithm

Let us first enumerate the cases where n is 0,1,2,3,4:

n = 0: none

n = 1: 0, 1, 8

n = 2: 11, 69, 88, 96

n = 3: 101, 609, 808, 906, 111, 619, 818, 916, 181, 689, 888, 986

n = 4: 1001, 6009, 8008, 9006, 1111, 6119, 8118, 9116, 1691, 6699, 8698, 9696, 1881, 6889, 8888, 9886, 1961, 6969, 8968, 9966


Pay attention to the observation of n=0 and n=2, you can find that the latter is based on the former, and the left and right sides of each number are increased by [1 1], [6 9], [8 8], [9 6]

Look at n=1 and n=3, it’s more obvious, increase [1 1] around 0, become 101, increase around 0 [6 9], become 609, increase around 0 [8 8] , Becomes 808, increases [9 6] to the left and right of 0, becomes 906, and then adds the four sets of numbers to the left and right sides of 1 and 8 respectively

In fact, it starts from the m=0 layer and adds layer by layer. It should be noted that when the n layer is added.

[0 0] cannot be added to the left and right sides, because 0 cannot appear at the beginning of two or more digits. In the process of recursive in the middle, it is necessary to add 0 to the left and right sides of the number.

# Code

• import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Strobogrammatic_Number_II {

public static void main(String[] args) {
Strobogrammatic_Number_II out = new Strobogrammatic_Number_II();
Solution s = out.new Solution();

System.out.println(s.findStrobogrammatic(2));
}

class Solution {

List<String> singleDigitList = new ArrayList<>(Arrays.asList("0", "1", "8")); // not char[], because List can direct return as result
char[][] digitPair = { {'1', '1'}, {'8', '8'}, {'6', '9'}, {'9', '6'} }; // except '0', a special case

public List<String> findStrobogrammatic(int n) {
return dfs(n, n);
}

public List<String> dfs(int k, int n) {
if (k <= 0) {
return new ArrayList<String>(Arrays.asList(""));
}
if (k == 1) {
return singleDigitList;
}

List<String> subList = dfs(k - 2, n);
List<String> result = new ArrayList<>();

for (String str : subList) {
}
for (char[] aDigitPair : digitPair) {
}
}

return result;
}
}

}

############

class Solution {
private static final int[][] PAIRS = { {1, 1}, {8, 8}, {6, 9}, {9, 6}};
private int n;

public List<String> findStrobogrammatic(int n) {
this.n = n;
return dfs(n);
}

private List<String> dfs(int u) {
if (u == 0) {
return Collections.singletonList("");
}
if (u == 1) {
return Arrays.asList("0", "1", "8");
}
List<String> ans = new ArrayList<>();
for (String v : dfs(u - 2)) {
for (var p : PAIRS) {
}
if (u != n) {
}
}
return ans;
}
}

• // OJ: https://leetcode.com/problems/strobogrammatic-number-ii/
// Time: O(5^(N/2))
// Space: O(N)
const char pairs[5][2] = { {'0','0'},{'1','1'},{'8','8'},{'6','9'},{'9','6'} };
class Solution {
public:
vector<string> findStrobogrammatic(int n) {
string s(n, '0');
vector<string> ans;
function<void(int)> dfs = [&](int i) {
if (i == (n + 1) / 2) {
ans.push_back(s);
return;
}
int j = n - 1 - i;
for (auto &[a, b] : pairs) {
if (i == j && a != b) continue;
if (i == 0 && n > 1 && a == '0') continue;
s[i] = a;
s[j] = b;
dfs(i + 1);
}
};
dfs(0);
return ans;
}
};

• '''
>>> l,r="ab"
>>> l
'a'
>>> r
'b'

>>> l,r="abc"
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ValueError: too many values to unpack (expected 2)
'''

class Solution:
def findStrobogrammatic(self, n: int) -> List[str]:
def dfs(u):
if u == 0:
return ['']
if u == 1:
return ['0', '1', '8']
ans = []
for v in dfs(u - 2):
for l, r in ('11', '88', '69', '96'):
ans.append(l + v + r)
if u != n:
ans.append('0' + v + '0')
return ans

return dfs(n)

############

class Solution(object):
def findStrobogrammatic(self, n):
"""
:type n: int
:rtype: List[str]
"""
self.d = {"0": "0", "1": "1", "6": "9", "8": "8", "9": "6"}

def dfs(half, path, res, n):
if len(path) == half:
pathStr = "".join(path)
if half * 2 == n: # half is even chars
res.append(pathStr + "".join([self.d[x] for x in pathStr[::-1]]))
else:
for c in "018": # half with odd chars
res.append(pathStr + c + "".join([self.d[x] for x in pathStr[::-1]]))
return

for c in "01689":
if c == "0" and len(path) == 0:
continue
path.append(c)
dfs(half, path, res, n)
path.pop()

res = []
dfs(n / 2, [], res, n)
return res


• func findStrobogrammatic(n int) []string {
var dfs func(int) []string
dfs = func(u int) []string {
if u == 0 {
return []string{""}
}
if u == 1 {
return []string{"0", "1", "8"}
}
var ans []string
pairs := [][]string{ {"1", "1"}, {"8", "8"}, {"6", "9"}, {"9", "6"} }
for _, v := range dfs(u - 2) {
for _, p := range pairs {
ans = append(ans, p[0]+v+p[1])
}
if u != n {
ans = append(ans, "0"+v+"0")
}
}
return ans
}
return dfs(n)
}