Google
247 Strobogrammatic Number II

1. Question

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.
For example, Given n = 2, return["11","69","88","96"].

2. Implementation

(1) DFS
1
public class Solution {
2
public List<String> findStrobogrammatic(int n) {
3
List<String> res = new ArrayList<>();
4
5
if (n <= 0) {
6
return res;
7
}
8
9
char[] num1 = {'0', '1', '8', '6', '9'};
10
char[] num2 = {'0', '1', '8', '9', '6'};
11
12
char[] buffer = new char[n];
13
14
dfs(buffer, num1, num2, res, 0);
15
return res;
16
}
17
18
public void dfs(char[] buffer, char[] num1, char[] num2, List<String> res, int index) {
19
int left = index;
20
int right = buffer.length - index - 1;
21
22
if (left > right) {
23
res.add(new String(buffer));
24
return;
25
}
26
27
// We can only fill in 0, 1, 8 in the middle index
28
if (left == right) {
29
for (int i = 0; i < 3; i++) {
30
buffer[left] = num1[i];
31
dfs(buffer, num1, num2, res, index + 1);
32
}
33
}
34
else {
35
for (int i = 0; i < num1.length; i++) {
36
// First digit can not be 0
37
if (index == 0 && i == 0) {
38
continue;
39
}
40
buffer[left] = num1[i];
41
buffer[right] = num2[i];
42
dfs(buffer, num1, num2, res, index + 1);
43
}
44
}
45
}
46
}
Copied!

3. Time & Space Complexity

DFS: 时间复杂度O(5^(n/2)), 空间复杂度O(n)