# 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:

```python
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

| Item | Meaning |
|---|---|
| Input | Two strings, `low` and `high` |
| Output | Count of strobogrammatic numbers in `[low, high]` |
| Range | Inclusive |
| Constraint | Numbers are represented as strings |
| Length | `1 <= len(low), len(high) <= 15` |

Example function shape:

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

## Examples

Example 1:

```python
low = "50"
high = "100"
```

The strobogrammatic numbers in this range are:

```python
69, 88, 96
```

So the answer is:

```python
3
```

Example 2:

```python
low = "0"
high = "0"
```

The only number in the range is `"0"`.

`"0"` is strobogrammatic.

So the answer is:

```python
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:

```python
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:

| Left Digit | Right Digit |
|---|---|
| `0` | `0` |
| `1` | `1` |
| `6` | `9` |
| `8` | `8` |
| `9` | `6` |

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

```python
"0", "1", "8"
```

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

```python
len(low)
```

and:

```python
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:

```python
"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:

```python
left = 0
right = n - 1
```

At each recursive step, place one valid pair:

```python
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.

| Metric | Value | Why |
|---|---|---|
| Time | `O(R * L)` | Each completed candidate may be joined and compared |
| Space | `O(L)` excluding output | DFS uses one character array and recursion depth `L` |

`L` is `len(high)`.

A loose upper bound for generated candidates is about:

```python
5^(L / 2)
```

because each mirrored layer has at most five choices.

## Implementation

```python
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:

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

The answer counts valid numbers:

```python
answer = 0
```

The DFS fills a character array from the outside inward.

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

When `left > right`, every position has been filled:

```python
candidate = "".join(chars)
```

Then we reject invalid leading zeros:

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

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

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

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

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

If the candidate passes all checks, we count it:

```python
answer += 1
```

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

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

Then we place the pair and recurse inward:

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

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

The outer loop generates candidates for every possible length:

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

## Testing

```python
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()
```

| Test | Why |
|---|---|
| `"50"` to `"100"` | Standard example |
| `"0"` to `"0"` | Single zero case |
| `"1"` to `"1"` | Single valid digit |
| `"2"` to `"2"` | Single invalid digit |
| `"0"` to `"10"` | Counts `0`, `1`, and `8` |
| `"10"` to `"100"` | Counts two-digit strobogrammatic numbers |
| `"100"` to `"999"` | Counts three-digit strobogrammatic numbers |