StroboGrammatic Number III

XXX. Strobogrammatic Number III

Recursion

String

Problem Statement:

A strobogrammatic number is a number that looks the same when rotated 180 degrees (e.g., 69, 88, 96). Given two numbers low and high, return the total count of strobogrammatic numbers within this range.

Algorithm:

1. Define the valid strobogrammatic pairs (0-0, 1-1, 6-9, 8-8, 9-6).
2. Use a depth-first search (DFS) to generate all possible strobogrammatic numbers of lengths between low.length() and high.length().
3. For each generated number, check if it is within the range defined by low and high.
4. Keep track of the count of valid numbers using an array.
5. Ensure leading zeros and invalid numbers (e.g., middle digit of odd-length numbers being non-strobogrammatic) are skipped during DFS.

Complexity:

Time Complexity: O(5^n/2), where n is the maximum length of the numbers.
Space Complexity: O(n) for the recursion stack.

Java Implementation:

public class Solution {
    private static final char[][] pairs = {
        {'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'}, {'9', '6'}
    };

    public int strobogrammaticInRange(String low, String high) {
        int[] count = {0};
        for (int len = low.length(); len <= high.length(); len++) {
            char[] c = new char[len];
            dfs(low, high, c, 0, len - 1, count);
        }
        return count[0];
    }

    private void dfs(String low, String high, char[] c, int left, int right, int[] count) {
        if (left > right) {
            String s = new String(c);
            if ((s.length() == low.length() && s.compareTo(low) < 0) || 
                (s.length() == high.length() && s.compareTo(high) > 0)) {
                return;
            }
            count[0]++;
            return;
        }
        for (char[] p : pairs) {
            c[left] = p[0];
            c[right] = p[1];
            if (c.length != 1 && c[0] == '0') continue; // Skip leading zeros
            if (left == right && p[0] != p[1]) continue; // Skip invalid middle digit
            dfs(low, high, c, left + 1, right - 1, count);
        }
    }
}
                

Python Implementation:

def strobogrammatic_in_range(low: str, high: str) -> int:
    pairs = [('0', '0'), ('1', '1'), ('6', '9'), ('8', '8'), ('9', '6')]
    count = [0]

    def dfs(c, left, right):
        if left > right:
            s = ''.join(c)
            if (len(s) == len(low) and s < low) or (len(s) == len(high) and s > high):
                return
            count[0] += 1
            return

        for a, b in pairs:
            c[left], c[right] = a, b
            if len(c) > 1 and c[0] == '0':
                continue  # Skip leading zeros
            if left == right and a != b:
                continue  # Skip invalid middle digit
            dfs(c, left + 1, right - 1)

    for length in range(len(low), len(high) + 1):
        dfs([''] * length, 0, length - 1)

    return count[0]
                

C++ Implementation:

#include 
#include 
#include 
using namespace std;

class Solution {
public:
    int strobogrammaticInRange(string low, string high) {
        vector> pairs = {{'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'}, {'9', '6'}};
        int count = 0;

        auto dfs = [&](auto&& self, vector& c, int left, int right) -> void {
            if (left > right) {
                string s(c.begin(), c.end());
                if ((s.length() == low.length() && s < low) || (s.length() == high.length() && s > high))
                    return;
                count++;
                return;
            }

            for (auto& [a, b] : pairs) {
                c[left] = a;
                c[right] = b;
                if (c.size() > 1 && c[0] == '0') continue; // Skip leading zeros
                if (left == right && a != b) continue; // Skip invalid middle digit
                self(self, c, left + 1, right - 1);
            }
        };

        for (int len = low.length(); len <= high.length(); ++len) {
            vector c(len);
            dfs(dfs, c, 0, len - 1);
        }

        return count;
    }
};