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
public class Solution {
public List<String> findStrobogrammatic(int n) {
List<String> res = new ArrayList<>();
if (n <= 0) {
return res;
}
char[] num1 = {'0', '1', '8', '6', '9'};
char[] num2 = {'0', '1', '8', '9', '6'};
char[] buffer = new char[n];
dfs(buffer, num1, num2, res, 0);
return res;
}
public void dfs(char[] buffer, char[] num1, char[] num2, List<String> res, int index) {
int left = index;
int right = buffer.length - index - 1;
if (left > right) {
res.add(new String(buffer));
return;
}
// We can only fill in 0, 1, 8 in the middle index
if (left == right) {
for (int i = 0; i < 3; i++) {
buffer[left] = num1[i];
dfs(buffer, num1, num2, res, index + 1);
}
}
else {
for (int i = 0; i < num1.length; i++) {
// First digit can not be 0
if (index == 0 && i == 0) {
continue;
}
buffer[left] = num1[i];
buffer[right] = num2[i];
dfs(buffer, num1, num2, res, index + 1);
}
}
}
}