247.Strobogrammatic Number II

1-Recursion

class Solution {
    public List<String> findStrobogrammatic(int n) {
        Map<Character, Character> map = new HashMap<>();
        map.put('0', '0');
        map.put('1', '1');
        map.put('6', '9');
        map.put('8', '8');
        map.put('9', '6');
        List<String> ans = new ArrayList<>();
        helper(map, ans, new char[n], 0, n - 1, n);
        return ans;
    }
    public void helper(Map<Character, Character> map, List<String> ans, char[] tmp,  int left, int right, int n){
        if(left > right){
            if(n > 1 && tmp[0] == '0')
                return ;
            else
                ans.add(new String(tmp));
        }
        else if(left == right){
            //Ugly Coding
            tmp[left] = '0';
            helper(map, ans, tmp, left + 1, right - 1, n);
            tmp[left] = '1';
            helper(map, ans, tmp, left + 1, right - 1, n);
            tmp[left] = '8';
            helper(map, ans, tmp, left + 1, right - 1, n);
        }
        else{
            for(Character c : map.keySet()){
                char val = map.get(c);
                tmp[left] = c;
                tmp[right] = val;
                helper(map, ans, tmp, left + 1, right - 1, n);
            }
        }
    }
}

2

public List<String> findStrobogrammatic(int n) {
    return helper(n, n);
}

List<String> helper(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> list = helper(n - 2, m);

    List<String> res = new ArrayList<String>();

    for (int i = 0; i < list.size(); i++) {
        String s = list.get(i);

        if (n != m) res.add("0" + s + "0");

        res.add("1" + s + "1");
        res.add("6" + s + "9");
        res.add("8" + s + "8");
        res.add("9" + s + "6");
    }

    return res;
}