# LeetCode 246: Strobogrammatic Number

## Problem Restatement

We are given a string `num` that represents an integer.

We need to return `true` if the number looks the same after being rotated `180` degrees. Otherwise, return `false`.

Only some digits are valid after rotation:

| Digit | Rotates To |
|---|---|
| `0` | `0` |
| `1` | `1` |
| `6` | `9` |
| `8` | `8` |
| `9` | `6` |

Digits like `2`, `3`, `4`, `5`, and `7` cannot appear in a valid rotated number.

The constraints say `1 <= num.length <= 50`, `num` contains only digits, and there are no leading zeros except for `"0"` itself.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A string `num` |
| Output | `True` if `num` is strobogrammatic, otherwise `False` |
| Constraint | `num` contains only digits |
| Length | `1 <= len(num) <= 50` |

Example function shape:

```python
def isStrobogrammatic(num: str) -> bool:
    ...
```

## Examples

Example 1:

```python
num = "69"
```

After rotation:

```python
6 -> 9
9 -> 6
```

The rotated number still matches the original shape.

So the answer is:

```python
True
```

Example 2:

```python
num = "88"
```

Both digits remain `8` after rotation.

So the answer is:

```python
True
```

Example 3:

```python
num = "962"
```

The digit `2` has no valid rotated form.

So the answer is:

```python
False
```

## First Thought

One direct way is to build the rotated version of the string.

For each digit, replace it with its rotated digit. Then reverse the result, because rotating the whole number also swaps left and right positions.

If the final string equals the original string, the number is strobogrammatic.

```python
class Solution:
    def isStrobogrammatic(self, num: str) -> bool:
        rotate = {
            "0": "0",
            "1": "1",
            "6": "9",
            "8": "8",
            "9": "6",
        }

        rotated = []

        for digit in num:
            if digit not in rotate:
                return False

            rotated.append(rotate[digit])

        return "".join(reversed(rotated)) == num
```

This works, but it builds an extra list.

We can check the same condition directly with two pointers.

## Key Insight

When the number is rotated `180` degrees, two things happen:

1. Each digit changes according to the rotation rule.
2. The order is reversed.

So the leftmost digit must rotate into the rightmost digit.

The second digit must rotate into the second-to-last digit.

This is similar to checking a palindrome, but instead of checking equal characters, we check rotated pairs.

For example:

```python
num = "69"
```

The left digit is `6`.

The right digit is `9`.

Since:

```python
rotate["6"] == "9"
```

the pair is valid.

## Algorithm

Create a rotation map:

```python
rotate = {
    "0": "0",
    "1": "1",
    "6": "9",
    "8": "8",
    "9": "6",
}
```

Use two pointers:

```python
left = 0
right = len(num) - 1
```

While `left <= right`:

1. Read `num[left]`.
2. Read `num[right]`.
3. If `num[left]` cannot be rotated, return `False`.
4. If `rotate[num[left]] != num[right]`, return `False`.
5. Move both pointers inward.

If all pairs are valid, return `True`.

## Correctness

The rotation of a full number reverses the positions of its digits.

Therefore, for every index `left`, the digit at `left` must rotate into the digit at the mirrored index `right`.

The algorithm checks exactly these mirrored pairs.

If a digit cannot be rotated, the number cannot be strobogrammatic, so returning `False` is correct.

If a digit rotates into a value different from its mirrored digit, the rotated number differs from the original number, so returning `False` is correct.

If every mirrored pair passes the check, then every digit becomes exactly the digit needed at its rotated position. Therefore, the whole number looks the same after rotation, so returning `True` is correct.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each digit is checked at most once |
| Space | `O(1)` | The rotation map has fixed size |

## Implementation

```python
class Solution:
    def isStrobogrammatic(self, num: str) -> bool:
        rotate = {
            "0": "0",
            "1": "1",
            "6": "9",
            "8": "8",
            "9": "6",
        }

        left = 0
        right = len(num) - 1

        while left <= right:
            if num[left] not in rotate:
                return False

            if rotate[num[left]] != num[right]:
                return False

            left += 1
            right -= 1

        return True
```

## Code Explanation

The map stores the only valid rotations:

```python
rotate = {
    "0": "0",
    "1": "1",
    "6": "9",
    "8": "8",
    "9": "6",
}
```

The two pointers start at both ends of the string:

```python
left = 0
right = len(num) - 1
```

For each mirrored pair, we first check whether the left digit can rotate:

```python
if num[left] not in rotate:
    return False
```

Then we check whether its rotated value equals the right digit:

```python
if rotate[num[left]] != num[right]:
    return False
```

If the pair is valid, both pointers move inward:

```python
left += 1
right -= 1
```

If every pair is valid, the number is strobogrammatic:

```python
return True
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.isStrobogrammatic("69") is True
    assert s.isStrobogrammatic("88") is True
    assert s.isStrobogrammatic("962") is False
    assert s.isStrobogrammatic("1") is True
    assert s.isStrobogrammatic("2") is False
    assert s.isStrobogrammatic("818") is True
    assert s.isStrobogrammatic("619") is True
    assert s.isStrobogrammatic("689") is True

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `"69"` | Checks the `6` and `9` pair |
| `"88"` | Checks unchanged digits |
| `"962"` | Checks invalid digit rejection |
| `"1"` | Checks one-character valid center |
| `"2"` | Checks one-character invalid center |
| `"818"` | Checks odd-length valid number |
| `"619"` | Checks multiple rotated pairs |
| `"689"` | Checks mixed valid rotations |