public class Solution {
public List findStrobogrammatic(int n) {
List res = new LinkedList();
String[] pair = {"00","11","88","69","96"};
char[] c = new char[n];
//将res，辅助char数组c，字符串对，开始构造字符串的初始位置，字符串长度，要求字符长度传入构造方法
helper(res, c, pair, 0, n, n);
return res;
}
private void helper(List<String> res, char[] c, String[] pair, int index, int length, int n) {
if(length == 0) {
res.add(String.valueOf(c));
return;
}
if(length == 1) {
for(int i = 0; i <= 2; i++) {
c[index] = pair[i].charAt(0);
res.add(String.valueOf(c));
}
return;
}
int start = (length == n ? 1 : 0);
for(int i = start; i < pair.length; i++) {
c[index] = pair[i].charAt(0);
c[index+length-1] = pair[i].charAt(1);
helper(res, c, pair, index+1, length-2, n);
}
}
Shawngbk
commented
7 years ago
可以像是一层层的给字符串从里向外穿衣服一样DFS生成所有的解.
其中翻转之后和自身相等有0, 1, 8, 在n为奇数的情况下最里面的一个数可以为这三个数的任意一个. 再外边就一次给两端添加一个对称的字符. 如果是最外层的话需要注意不能是为0. 最后一个for循环因为每次都要DFS调用helper函数，所以能够列举出每一种情况 return作用是在满足情况下返回操作权
public class Solution { public List findStrobogrammatic(int n) {
List res = new LinkedList();
String[] pair = {"00","11","88","69","96"};
char[] c = new char[n];
//将res，辅助char数组c，字符串对，开始构造字符串的初始位置，字符串长度，要求字符长度传入构造方法
helper(res, c, pair, 0, n, n);
return res;
}
}