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
Given n = 2, return
["11","69","88","96"]
.
Solution 1: back tracking to build all the numbers.
public class Solution {
public List<String> findStrobogrammatic(int n) {
List<String> res=new ArrayList<>();
if (n<=0) return res;
char[] c=new char[n];
dfs(c,0,n-1,res);
return res;
}
private void dfs(char[] c, int i, int j, List<String> res) {
if (i>j) res.add(new String(c));
else {
if (i>0 || (i==0 && j==0)) {
c[i]='0';c[j]='0';
dfs(c,i+1,j-1,res);
}
if (i!=j) {
c[i]='6';c[j]='9';
dfs(c,i+1,j-1,res);
c[i]='9';c[j]='6';
dfs(c,i+1,j-1,res);
}
c[i]='1';c[j]='1';
dfs(c,i+1,j-1,res);
c[i]='8';c[j]='8';
dfs(c,i+1,j-1,res);
}
}
}
没有评论:
发表评论