247 Strobogrammatic Number II

247. Strobogrammatic Number II

1. Question

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

2. Implementation

(1) DFS

public class Solution {
    public List<String> findStrobogrammatic(int n) {
        List<String> res = new ArrayList<>();

        if (n <= 0) {
            return res;
        }

        char[] num1 = {'0', '1', '8', '6', '9'};
        char[] num2 = {'0', '1', '8', '9', '6'};

        char[] buffer = new char[n];

        dfs(buffer, num1, num2, res, 0);
        return res;
    }

    public void dfs(char[] buffer, char[] num1, char[] num2, List<String> res, int index) {
        int left = index;
        int right = buffer.length - index - 1;

        if (left > right) {
            res.add(new String(buffer));
            return;
        }

        // We can only fill in 0, 1, 8 in the middle index
        if (left == right) {
            for (int i = 0; i < 3; i++) {
                buffer[left] = num1[i];
                dfs(buffer, num1, num2, res, index + 1);
            }
        }
        else {
            for (int i = 0; i < num1.length; i++) {
                // First digit can not be 0
                if (index == 0 && i == 0) {
                    continue;
                }
                buffer[left] = num1[i];
                buffer[right] = num2[i];
                dfs(buffer, num1, num2, res, index + 1);
            }
        }
    }
}

3. Time & Space Complexity

DFS: 时间复杂度O(5^(n/2))， 空间复杂度O(n)