BiruLyu
8/5/2017 - 6:02 PM

## 247. Strobogrammatic Number II(#recursive).java

``````public class Solution {
public List<String> findStrobogrammatic(int n) {
List<String> one = Arrays.asList("0", "1", "8"), two = Arrays.asList(""), r = two;
if(n%2 == 1)
r = one;
for(int i=(n%2)+2; i<=n; i+=2){
List<String> newList = new ArrayList<>();
for(String str : r){
if(i != n)
}
r = newList;
}
return r;
}

}``````
``````public class Solution {
char[][] pairs = new char[][]{{'0', '0'}, {'1', '1'}, {'8', '8'}, {'6', '9'}, {'9', '6'}};
public List<String> findStrobogrammatic(int n) {
List<String> res = new ArrayList<>();
char[] build = new char[n];
dfs(res, build, 0, n - 1);
return res;
}
private void dfs(List<String> res, char[] build, int left, int right){
if(left > right){
String s = new String(build);
return;
}
for(int i = 0; i < pairs.length; i++){
build[left] = pairs[i][0];
build[right] = pairs[i][1];
if(build.length > 1 && build[0] == '0') continue;
if(left == right){
if(i == 3 || i == 4) continue;
}
dfs(res, build, left + 1, right - 1);
}
}
}``````
``````public class Solution {
private char[][] stroNums = {{'0', '0'}, {'1', '1'}, {'8','8'}, {'6', '9'}, {'9', '6'}};

public List<String> findStrobogrammatic(int n) {
List<String> res = new ArrayList<>();
char[] ra = new char[n];
if (n % 2 == 0) {
setResults(res, ra, n/2 - 1);
} else {
ra[n/2] = '1';
setResults(res, ra, n/2 - 1);
ra[n/2] = '8';
setResults(res, ra, n/2 - 1);
ra[n/2] = '0';
setResults(res, ra, n/2 - 1);
}

return res;
}

private void setResults(List<String> res, char[] ra, int pos) {
if (pos < 0) {
return;
}

for (char[] sc : stroNums) {
if (pos == 0 && sc[0] == '0') continue;

ra[pos] = sc[0];
ra[ra.length - 1 - pos] = sc[1];
setResults(res, ra, pos - 1);
}
}
}``````
``````public class Solution {
private List<String> generate(int left, int amount) {
if (left == 0) return new ArrayList<String>(Arrays.asList(""));
if (left == 1) return new ArrayList<String>(Arrays.asList("0", "1", "8"));

List<String> mid = generate(left - 2, amount);

List<String> res = new ArrayList<>();
for (String s : mid) {
if (left != amount) {