首页 > 代码库 > 247. Strobogrammatic Number II

247. Strobogrammatic Number II

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"].

 

 

dfs

public class Solution {    //dfs    //考虑 0110的状况 主要是去掉0    public List<String> findStrobogrammatic(int n) {        List<String> member = new ArrayList<>();        member = dfs(n, n);          return member;    }    public List<String> dfs(int n , int m) {        if(n == 0) {            ArrayList<String> member = new ArrayList<>();            member.add("");            return new ArrayList<>(member);        }        if(n == 1) {            ArrayList<String> member = new ArrayList<>();            member.add("0");            member.add("1");            member.add("8");            return new ArrayList<>(member);        }        List<String> list = dfs(n - 2, m);        ArrayList<String> newList = new ArrayList<String>(); // from bottom to top consider 0        for(int i = 0 ; i< list.size(); i++){            newList.add("1" + list.get(i) + "1");            newList.add("6" + list.get(i) + "9");            newList.add("9" + list.get(i) + "6");            newList.add("8" + list.get(i) + "8");            if(n != m) //去0 like 0110, 0880                newList.add("0" + list.get(i) + "0");        }        return newList;    }    }

 

from bottom to up consider 0 like n =4 0110,0000

 

247. Strobogrammatic Number II