248.Strobogrammatic Number III

Tags: Hard Recursion

Links: https://leetcode-cn.com/problems/strobogrammatic-number-iii/

---

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

Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.

Example:

Input: low = "50", high = "100"
Output: 3 
Explanation: 69, 88, and 96 are three strobogrammatic numbers.

Note:

Because the range might be a large number, the low and high numbers are represented as string.

---

class Solution {
    unordered_map<int, vector<string>> um{{0, {""}}, {1, {"1", "8", "0"}}};
public:
    int strobogrammaticInRange(string low, string high) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        if (low.size() > high.size() || (low.size() == high.size() && low > high))
            return 0;

        int left = low.size(), right = high.size();
        int cnt = 0;
        for (int i = left + 1; i <= right - 1; ++i) {
            um[i] = build(i, i);
            cnt += um[i].size();
        }

        if (left == right) {
            um[left] = build(left, left);
            for (auto & e : um[left]) {
                if (low <= e && e <= high) ++cnt;
            }
        }
        else {
            um[left] = build(left, left);
            for (auto &e : um[left]) {
                if (e >= low) ++cnt;
            }

            um[right] = build(right, right);
            for (auto &e: um[right]) {
                if (e <= high) ++cnt;
            }
        }

        return cnt;
    }

    vector<string> build(int m, int n)
    {
        if (m == 0) return {""};
        if (m == 1) return {"1", "8", "0"};

        vector<string> tmp = build(m - 2, n), res;
        for (auto &e : tmp) {
            if (m != n) res.push_back("0" + e + "0");
            res.push_back("1" + e + "1");
            res.push_back("8" + e + "8");
            res.push_back("6" + e + "9");
            res.push_back("9" + e + "6");
        }

        return res;
    }
};

最开始的思路是利用一个map来保留中间产生的结果，下一次生成的时候，如果已经产生过了，那么就不用再重新buil，直接O(1)返回即可。但是这样就会产生一个不易察觉的bug，考虑长度为4的时候进行build，那么递归到n = 2，因为此时m != n，所以res里面有"00"，然后会替换掉正常的n = 2的vector，而实际上这个是不满足。

所以可以分为两部分考虑，长度比low大，比high小的，直接build，它的数组长度就是个数，直接加入到cnt即可，到了长度为low和high单独考虑。