247. Strobogrammatic Number II

// LeetCode URL: https://leetcode.com/problems/strobogrammatic-number-ii/
import java.util.ArrayList;
import java.util.List;

/**
 * Recursive Backtracking using char array
 *
 * Time Complexity : O(5 ^ (N/2))
 *
 * Space Complexity: O(N). There will be maximum N/2 levels in recursion stack.
 *
 * N = input number.
 */
class Solution1 {
    public static final char[][] PAIRS = new char[][] { { '0', '0' }, { '1', '1' }, { '6', '9' }, { '8', '8' },
            { '9', '6' } };

    public List<String> findStrobogrammatic(int n) {
        ArrayList<String> result = new ArrayList<>();
        if (n < 0) {
            return result;
        }

        dfsHelper(result, new char[n], 0, n - 1);

        return result;
    }

    private void dfsHelper(ArrayList<String> list, char[] chArr, int left, int right) {
        if (left > right) {
            list.add(new String(chArr));
            return;
        }

        for (char[] p : PAIRS) {
            if (chArr.length > 1 && left == 0 && p[0] == '0') {
                continue;
            }
            if (left == right && p[0] != p[1]) {
                continue;
            }
            chArr[left] = p[0];
            chArr[right] = p[1];
            dfsHelper(list, chArr, left + 1, right - 1);
        }
    }
}

/**
 * Recursive Backtracking Using temp strings
 *
 * Time Complexity : O(5 ^ (N/2))
 *
 * Space Complexity: O(N ^ 2). There will be maximum N/2 levels in recursion
 * stack.
 *
 * N = input number.
 */
class Solution2 {
    public List<String> findStrobogrammatic(int n) {
        ArrayList<String> result = new ArrayList<>();
        if (n < 0) {
            return result;
        }
        if (n % 2 == 0) {
            dfsHelper(result, "", n);
        } else {
            dfsHelper(result, "0", n);
            dfsHelper(result, "1", n);
            dfsHelper(result, "8", n);
        }

        return result;
    }

    private void dfsHelper(ArrayList<String> list, String tempStr, int n) {
        if (tempStr.length() == n) {
            if (n > 1 && tempStr.charAt(0) == '0') {
                return;
            }
            list.add(tempStr.toString());
            return;
        }

        dfsHelper(list, "0" + tempStr + "0", n);
        dfsHelper(list, "1" + tempStr + "1", n);
        dfsHelper(list, "8" + tempStr + "8", n);
        dfsHelper(list, "6" + tempStr + "9", n);
        dfsHelper(list, "9" + tempStr + "6", n);
    }
}

/**
 * Recursive
 *
 * Time Complexity : O(5 ^ (N/2))
 *
 * Space Complexity: O(N * 5 ^ (N/2)). There will be 5 ^ ((N-2)/2) strings of
 * N-2 length at level before result level.
 *
 * N = input number.
 */
class Solution3 {
    public List<String> findStrobogrammatic(int n) {
        if (n < 0) {
            return new ArrayList<>();
        }

        return dfsHelper(n, n);
    }

    private ArrayList<String> dfsHelper(int m, int n) {
        ArrayList<String> res = new ArrayList<>();
        if (m == 0) {
            res.add("");
            return res;
        }
        if (m == 1) {
            res.add("0");
            res.add("1");
            res.add("8");
            return res;
        }

        ArrayList<String> list = dfsHelper(m - 2, n);

        for (String s : list) {
            if (m != n) {
                res.add("0" + s + "0");
            }
            res.add("1" + s + "1");
            res.add("8" + s + "8");
            res.add("6" + s + "9");
            res.add("9" + s + "6");
        }
        return res;
    }
}

/**
 * Iterative
 *
 * Time Complexity : O(5 ^ (N/2))
 *
 * Space Complexity: O(N * 5 ^ (N/2)). There will be 5 ^ ((N-2)/2) strings of
 * N-2 length at level before result level.
 *
 * N = input number.
 */
class Solution4 {
    public List<String> findStrobogrammatic(int n) {
        ArrayList<String> result = new ArrayList<>();
        if (n < 0) {
            return result;
        }
        if (n % 2 == 0) {
            result.add("");
        } else {
            result.add("0");
            result.add("1");
            result.add("8");
        }
        ArrayList<String> list;
        for (int i = n; i > 1; i -= 2) {
            list = result;
            result = new ArrayList<>();
            for (String s : list) {
                if (i > 3) {
                    result.add("0" + s + "0");
                }
                result.add("1" + s + "1");
                result.add("8" + s + "8");
                result.add("6" + s + "9");
                result.add("9" + s + "6");
            }
        }
        return result;
    }
}