# 247. Strobogrammatic Number II

[Link](https://www.cnblogs.com/grandyang/p/5200919.html)

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.

Example:

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

**Solution**

由於strobogrammatic string可由之前長度較小(len-2)的strobogrammic string推導出來。

ex: 長度 1時的 :  1, 8, 0\
&#x20;     長度3的: **1**1**1, 6**1**9**, **9**1**6**, **8**1**8**, **1**8**1**, **6**8**9**, **9**8**6**, **8**8**8 ...**\
不過當數字是0時其實也是strobogrammatic string的元素之一, 但成立的條件是不要在外面 \
ex: 080 (X),   10801 (O)

所以在計算(len-2)的strobogrammic string必須加上 "0" + str + "0" 這種case。但最後要推導出len的strogrammic string時因為已經是最外面的，就不能做。

```
        List<String> sub = findStrobogrammatic(currentLength-2, targetLength);
        for (String str : sub
        ) {
            //REMEMBER only add 0xx0 for the non-edge condition (targetLength != currentLength)
            if(targetLength != currentLength) {
                ret.add("0" + str + "0");
            }
            ret.add("9" + str + "6");
            ret.add("6" + str + "9");
            ret.add("1" + str + "1");
            ret.add("8" + str + "8");
        }
```

因此另外設計一個function帶入兩個parameter來區別目前算的是疊代的(len-2) case還是是求最後len的case。

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

    /**
     * @param currentLength the current(temp) Strobogrammatic's length we trying to generate
     * @param targetLength the length of target Strobogrammatic string
     * @return if currentLength == targetLength:　the all strobogrammatic string which len is targetLength.
     *         otherwise it returns the sub-set which len is currentLength and includes 0xxx0 cases.
     */
    public static List<String> findStrobogrammatic(int currentLength, int targetLength) {
        List<String> ret = new ArrayList<>();
        if(currentLength == 0){
            ret.add("");
            return ret;
        }
        if(currentLength == 1){
            ret.add("8");
            ret.add("1");
            ret.add("0");
            return ret;
        }
        List<String> sub = findStrobogrammatic(currentLength-2, targetLength);
        for (String str : sub
        ) {
            //REMEMBER only add 0xx0 for the non-edge condition (targetLength != currentLength)
            if(targetLength != currentLength) {
                ret.add("0" + str + "0");
            }
            ret.add("9" + str + "6");
            ret.add("6" + str + "9");
            ret.add("1" + str + "1");
            ret.add("8" + str + "8");
        }
        return ret;
    }
```
