LeetCode 248: Strobogrammatic Number III

Problem Restatement

We are given two strings, low and high, representing two integers.

Return the number of strobogrammatic numbers in the inclusive range:

low <= num <= high

A strobogrammatic number looks the same after being rotated 180 degrees.

The numbers are represented as strings because the range can be large. The constraints say 1 <= low.length, high.length <= 15, low and high contain only digits, low <= high, and neither string has leading zeros except "0" itself.

Input and Output

Example function shape:

def strobogrammaticInRange(low: str, high: str) -> int:
    ...

Examples

Example 1:

low = "50"
high = "100"

The strobogrammatic numbers in this range are:

69, 88, 96

So the answer is:

3

Example 2:

low = "0"
high = "0"

The only number in the range is "0".

"0" is strobogrammatic.

So the answer is:

1

First Thought

We could check every number from low to high.

For each number, convert it to a string and check whether it is strobogrammatic.

This is too slow because the range may be very large.

For example:

low = "1"
high = "999999999999999"

The number of integers in the range is enormous.

We need to generate only strobogrammatic candidates.

Key Insight

A strobogrammatic number is built from mirrored digit pairs.

The valid pairs are:

For odd lengths, the center digit must rotate into itself:

"0", "1", "8"

So we can generate every strobogrammatic number for each possible length between:

len(low)

and:

len(high)

Then we count only the generated numbers that fall inside the range.

Since low and high are strings, comparison works directly only when the lengths are equal.

For example:

"88" < "100"

is false lexicographically, even though 88 < 100.

So we compare strings only when their lengths match.

Algorithm

For each length n from len(low) to len(high):

1. Generate all strobogrammatic numbers of length n.
2. Skip numbers with leading zero, except "0".
3. If n == len(low), skip values smaller than low.
4. If n == len(high), skip values greater than high.
5. Count the remaining values.

We can generate numbers with DFS.

Use a character array of size n.

Fill it from both ends:

left = 0
right = n - 1

At each recursive step, place one valid pair:

s[left] = pair_left
s[right] = pair_right

Then recurse inward.

When left > right, the string is complete. Check whether it is inside the range.

Correctness

The DFS places only valid rotated digit pairs. Therefore, every completed string produced by DFS is strobogrammatic.

For odd lengths, the middle position has left == right. In that case, the algorithm allows only pairs where both digits are equal, so the center can only be 0, 1, or 8.

The algorithm rejects leading zero strings when the total length is greater than 1. Therefore, every counted string is a valid integer representation.

The outer loop considers every length from len(low) through len(high). Any number inside [low, high] must have one of those lengths.

For numbers with the same length as low, the algorithm rejects strings smaller than low. For numbers with the same length as high, it rejects strings greater than high. For lengths strictly between them, all generated numbers are automatically inside the range by length.

Thus, the algorithm counts exactly all strobogrammatic numbers in [low, high].

Complexity

Let R be the number of generated strobogrammatic candidates across all considered lengths.

L is len(high).

A loose upper bound for generated candidates is about:

5^(L / 2)

because each mirrored layer has at most five choices.

Implementation

class Solution:
    def strobogrammaticInRange(self, low: str, high: str) -> int:
        pairs = [
            ("0", "0"),
            ("1", "1"),
            ("6", "9"),
            ("8", "8"),
            ("9", "6"),
        ]

        answer = 0

        def dfs(chars: list[str], left: int, right: int) -> None:
            nonlocal answer

            if left > right:
                candidate = "".join(chars)

                if len(candidate) > 1 and candidate[0] == "0":
                    return

                if len(candidate) == len(low) and candidate < low:
                    return

                if len(candidate) == len(high) and candidate > high:
                    return

                answer += 1
                return

            for a, b in pairs:
                if left == right and a != b:
                    continue

                chars[left] = a
                chars[right] = b

                dfs(chars, left + 1, right - 1)

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

        return answer

Code Explanation

The pairs list stores every valid mirrored pair:

pairs = [
    ("0", "0"),
    ("1", "1"),
    ("6", "9"),
    ("8", "8"),
    ("9", "6"),
]

The answer counts valid numbers:

answer = 0

The DFS fills a character array from the outside inward.

def dfs(chars: list[str], left: int, right: int) -> None:

When left > right, every position has been filled:

candidate = "".join(chars)

Then we reject invalid leading zeros:

if len(candidate) > 1 and candidate[0] == "0":
    return

We only compare with low when the candidate has the same length as low:

if len(candidate) == len(low) and candidate < low:
    return

We only compare with high when the candidate has the same length as high:

if len(candidate) == len(high) and candidate > high:
    return

If the candidate passes all checks, we count it:

answer += 1

For the middle digit of an odd-length number, we only allow self-rotating digits:

if left == right and a != b:
    continue

Then we place the pair and recurse inward:

chars[left] = a
chars[right] = b

dfs(chars, left + 1, right - 1)

The outer loop generates candidates for every possible length:

for length in range(len(low), len(high) + 1):

Testing

def run_tests():
    s = Solution()

    assert s.strobogrammaticInRange("50", "100") == 3
    assert s.strobogrammaticInRange("0", "0") == 1
    assert s.strobogrammaticInRange("1", "1") == 1
    assert s.strobogrammaticInRange("2", "2") == 0
    assert s.strobogrammaticInRange("0", "10") == 3
    assert s.strobogrammaticInRange("10", "100") == 4
    assert s.strobogrammaticInRange("100", "999") == 12

    print("all tests passed")

run_tests()