247. Strobogrammatic Number II

Link

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 長度3的: 111, 619, 916, 818, 181, 689, 986, 888 ... 不過當數字是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;
    }