247. Strobogrammatic Number II

Given an integer n, return all the strobogrammatic numbers that are of length n. You may return the answer in any order.

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Example 1:

Input: n = 2
Output: ["11","69","88","96"]

Example 2:

Input: n = 1
Output: ["0","1","8"]

Constraints:

• 1 <= n <= 14

Solution:

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

    public List<String> helper(int m, int n){
        if (m == 0){
            return Arrays.asList("");
        }

        if (m == 1){
            return Arrays.asList("0", "1", "8");
        }

        List<String> res = new ArrayList<>();
        List<String> list = helper(m - 2, n);
        for (String s : list){
            if (m != n){ // We should not add '0' to the beginning for the outermost layer
                res.add("0" + s + "0");
            }
            res.add("6" + s + "9");
            res.add("9" + s + "6");
            res.add("1" + s + "1");
            res.add("8" + s + "8");
        }

        return res;
    }
}

TC: O(\(5^{\frac{n}{2}}\)​)

TC: \(O(branch^{level})\) , branch = 5 , level : n/2. beacuse everytime n - 2

SC: \(O(n 5^{\frac{n}{2}} )\)​

空间复杂度主要来源于递归调用的栈空间和存储生成的结果：

• 递归的深度为 n2\frac{n}{2}2n，因此递归栈的空间复杂度为 O(n2)O(\frac{n}{2})O(2n)，即 O(n)O(n)O(n)。
• 结果的空间复杂度由最终生成的 strobogrammatic 数字组成。我们最多生成 O(5n2)O(5^{\frac{n}{2}})O(52n) 个字符串，并且每个字符串的长度为 n。

因此，总的空间复杂度为 O(n⋅5n2)O(n \cdot 5^{\frac{n}{2}})O(n⋅52n)，这是由于我们存储了所有长度为 n 的 strobogrammatic 数字。

graph TD
  A[findStrobogrammatic] --> B[helper n]
  B --> C[helper n-2]
  C --> D[helper n-4]
  D --> E[Base Case: return 0, 1, 8]

  B --> F[Generate pairs level 1]
  F --> G[0 + helper n-2 + 0]
  F --> H[1 + helper n-2 + 1]
  F --> I[6 + helper n-2 + 9]
  F --> J[8 + helper n-2 + 8]
  F --> K[9 + helper n-2 + 6]

  C --> L[Generate pairs level 2]
  L --> M[0 + helper n-4 + 0]
  L --> N[1 + helper n-4 + 1]
  L --> O[6 + helper n-4 + 9]
  L --> P[8 + helper n-4 + 8]
  L --> Q[9 + helper n-4 + 6]