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

tag: DFS, backtracking

class Solution {
    public List<String> findStrobogrammatic(int n) {
        return dfs(n, n);
    }

    private List<String> dfs(int n, int m){
        if (n == 0) return new ArrayList<String>(Arrays.asList(""));
        if (n == 1) return new ArrayList<String>(Arrays.asList("0", "1", "8"));

        List<String> subList = dfs(n - 2, m);
        List<String> ans = new ArrayList<>();

        for (String sub : subList){

            if (n != m) ans.add("0" + sub + "0");
            ans.add("1" + sub + "1");
            ans.add("8" + sub + "8");
            ans.add("6" + sub + "9");
            ans.add("9" + sub + "6");
        }

        return ans;
    }
}

class Solution {
    public List<String> findStrobogrammatic(int n) {
        List<String> ans = new ArrayList<>();
        Map<Character, Character> dict = new HashMap<>();
        dict.put('0', '0');
        dict.put('1', '1');
        dict.put('8', '8');
        dict.put('6', '9');
        dict.put('9', '6');

        return dfs(n, n, dict, ans);
    }

    private List<String> dfs(int n, int m, Map<Character, Character> dict, List<String> ans){
        if (n == 0){
            List<String> temp = new ArrayList<>();
            temp.add("");
            return temp;
        }

        if (n == 1){
            List<String> temp = new ArrayList<>();
            temp.add("0");
            temp.add("1");
            temp.add("8");

            return temp;
        }

        List<String> prev = dfs(n - 2, m, dict, ans);
        List<String> cur = new ArrayList<>();
        for (String str : prev){
            for (Character c : dict.keySet()){
                if (n == m && c == '0') continue;
                cur.add(c + str + dict.get(c));
            }
        }

        return cur;
    }
}