248

248. Strobogrammatic Number III (Hard)

Given two strings low and high that represent two integers low and high where low <= high, return the number of strobogrammatic numbers in the range [low, high].

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

 

Example 1:

Input: low = "50", high = "100"
Output: 3

Example 2:

Input: low = "0", high = "0"
Output: 1

 

Constraints:

• 1 <= low.length, high.length <= 15
• low and high consist of only digits.
• low <= high
• low and high do not contain any leading zeros except for zero itself.

Related Topics:
Array, String, Recursion

Similar Questions:

• Strobogrammatic Number (Easy)
• Strobogrammatic Number II (Medium)

Solution 1. DFS

// OJ: https://leetcode.com/problems/strobogrammatic-number-iii
// Author: github.com/lzl124631x
// Time: O(5^H)
// Space: O(H)
class Solution {
public:
    int strobogrammaticInRange(string low, string high) {
        unordered_map<int, int> m{{0,0},{1,1},{8,8},{6,9},{9,6}};
        string tmp;
        int ans = 0;
        function<void(int, int)> dfs = [&](int i, int len) {
            if (i > (len - 1) / 2) {
                ans += (len > low.size() || tmp >= low) && (len < high.size() || tmp <= high);
                return;
            }
            for (auto &[a, b] : m) {
                if (i == 0 && len > 1 && a == 0) continue; // first digit can't be 0 for multi-digit numbers
                if (i == len / 2 && a != b) continue; // the middle number must be identical after rotation
                tmp[i] = '0' + a;
                tmp[len - i - 1] = '0' + b;
                dfs(i + 1, len);
            }
        };
        for (int len = low.size(); len <= high.size(); ++len) {
            tmp = string(len, '0');
            dfs(0, len);
        }
        return ans;
    }
};