# LeetCode 816: Ambiguous Coordinates

## Problem Restatement

We are given a string `s` that represents a coordinate pair after removing commas, spaces, and decimal points.

For example:

```python
"(1, 3)" -> "(13)"
"(2, 0.5)" -> "(205)"
```

The string still contains the opening and closing parentheses.

We need to return all possible original coordinate strings.

The original coordinate representation had no unnecessary zeroes. So values like these are invalid:

```python
"00"
"001"
"0.0"
"1.0"
".1"
```

The final answer can be returned in any order, and each coordinate must use exactly this format:

```python
"(x, y)"
```

with one space after the comma. The official statement allows any result order.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A string like `"(123)"` |
| Output | All valid coordinate strings |
| Removed characters | Comma, space, and decimal point |
| Still present | Opening and closing parentheses |
| Output format | `"(x, y)"` |

## Examples

Example 1:

```python
s = "(123)"
```

Possible coordinates are:

```python
"(1, 23)"
"(1, 2.3)"
"(12, 3)"
"(1.2, 3)"
```

So a valid answer is:

```python
["(1, 23)", "(1, 2.3)", "(12, 3)", "(1.2, 3)"]
```

Example 2:

```python
s = "(0123)"
```

Some valid coordinates are:

```python
"(0, 123)"
"(0, 12.3)"
"(0, 1.23)"
"(0.1, 23)"
"(0.1, 2.3)"
"(0.12, 3)"
```

Values like `"01"` or `"012"` are invalid because they have leading zeroes.

Example 3:

```python
s = "(00011)"
```

A valid answer is:

```python
["(0, 0.011)", "(0.001, 1)"]
```

## First Thought: Try Every Split

The string inside the parentheses must be split into two non-empty parts:

```python
left + right
```

The left part becomes `x`.

The right part becomes `y`.

For each side, we also need to try every valid decimal placement.

So the problem has two levels of enumeration:

1. Split the digits into `x` and `y`.
2. Generate every valid number representation for each side.

## Key Insight

A substring can produce only a small number of valid numeric strings.

For a substring `part`, possible forms are:

```python
part
part[:i] + "." + part[i:]
```

But zero rules remove many candidates.

The validation rules are:

| Case | Valid? | Reason |
|---|---:|---|
| `"0"` | Yes | Single zero is allowed |
| `"00"` | No | Leading zero |
| `"01"` | No | Leading zero |
| `"0.1"` | Yes | Zero before decimal is allowed |
| `"0.01"` | Yes | Decimal does not end in zero |
| `"1.0"` | No | Trailing zero after decimal |
| `"10"` | Yes | Normal integer |
| `"10.5"` | Yes | Normal decimal |

So we can write a helper that returns all valid numeric strings from one digit substring.

## Algorithm

Remove the outer parentheses:

```python
digits = s[1:-1]
```

For every split position:

```python
left = digits[:i]
right = digits[i:]
```

Generate all valid numbers from `left`.

Generate all valid numbers from `right`.

For every valid pair `(x, y)`, append:

```python
f"({x}, {y})"
```

Return the answer list.

## Generating Valid Numbers

For a digit string `part`:

If its length is `1`, return it:

```python
["0"] or ["5"]
```

If it starts with `0` and ends with `0`, it has no valid form:

```python
"00" -> []
"000" -> []
```

If it starts with `0`, the only possible form is:

```python
"0." + part[1:]
```

This is valid only because it does not end with `0`.

If it ends with `0`, the only possible form is the integer itself:

```python
"10" -> ["10"]
```

Decimal forms like `"1.0"` are invalid.

Otherwise, return the integer form and every decimal placement.

## Correctness

The algorithm tries every possible split of the digits into two non-empty substrings. Therefore, every possible separation between `x` and `y` is considered.

For each side, the helper returns exactly the valid numeric representations that can be made by optionally inserting one decimal point.

It rejects integer forms with leading zeroes, except the single value `"0"`. It rejects decimal forms whose fractional part ends in zero. It also rejects decimal forms with invalid leading zeroes, except forms like `"0.xxx"`.

Every coordinate produced by the algorithm uses one valid representation from the left side and one valid representation from the right side, so every produced coordinate is valid.

Conversely, any valid original coordinate must correspond to some split of the digit string and some valid decimal placement in each side. The algorithm enumerates that split and those placements, so it includes that coordinate.

Therefore, the algorithm returns exactly all valid coordinate strings.

## Complexity

Let `n = len(s)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n^3)` | There are `O(n)` splits, each side can produce `O(n)` candidates, and formatting strings costs up to `O(n)` |
| Space | `O(n^3)` | The output itself can contain `O(n^2)` strings of length `O(n)` |

## Implementation

```python
class Solution:
    def ambiguousCoordinates(self, s: str) -> list[str]:
        digits = s[1:-1]

        def valid_numbers(part: str) -> list[str]:
            if len(part) == 1:
                return [part]

            if part[0] == "0" and part[-1] == "0":
                return []

            if part[0] == "0":
                return ["0." + part[1:]]

            if part[-1] == "0":
                return [part]

            result = [part]

            for i in range(1, len(part)):
                result.append(part[:i] + "." + part[i:])

            return result

        answer = []

        for i in range(1, len(digits)):
            left = digits[:i]
            right = digits[i:]

            for x in valid_numbers(left):
                for y in valid_numbers(right):
                    answer.append(f"({x}, {y})")

        return answer
```

## Code Explanation

We first remove the parentheses:

```python
digits = s[1:-1]
```

The helper function generates every valid number for one side:

```python
def valid_numbers(part: str) -> list[str]:
```

A one-digit number is always valid:

```python
if len(part) == 1:
    return [part]
```

If a multi-digit string starts and ends with zero, it cannot be valid:

```python
if part[0] == "0" and part[-1] == "0":
    return []
```

For example, `"00"` cannot be `"00"` or `"0.0"`.

If it starts with zero, only the decimal form can work:

```python
if part[0] == "0":
    return ["0." + part[1:]]
```

If it ends with zero, only the integer form can work:

```python
if part[-1] == "0":
    return [part]
```

Otherwise, both the integer form and all decimal placements are valid:

```python
result = [part]

for i in range(1, len(part)):
    result.append(part[:i] + "." + part[i:])
```

The outer loop chooses where to split the digits into `x` and `y`:

```python
for i in range(1, len(digits)):
```

Then every valid pair is formatted:

```python
answer.append(f"({x}, {y})")
```

## Testing

```python
def normalize(items):
    return sorted(items)

def run_tests():
    s = Solution()

    assert normalize(s.ambiguousCoordinates("(123)")) == normalize([
        "(1, 23)",
        "(1, 2.3)",
        "(12, 3)",
        "(1.2, 3)",
    ])

    assert normalize(s.ambiguousCoordinates("(0123)")) == normalize([
        "(0, 123)",
        "(0, 12.3)",
        "(0, 1.23)",
        "(0.1, 23)",
        "(0.1, 2.3)",
        "(0.12, 3)",
    ])

    assert normalize(s.ambiguousCoordinates("(00011)")) == normalize([
        "(0, 0.011)",
        "(0.001, 1)",
    ])

    assert normalize(s.ambiguousCoordinates("(100)")) == normalize([
        "(10, 0)",
    ])

    assert normalize(s.ambiguousCoordinates("(1010)")) == normalize([
        "(1, 010)",  # invalid, included here only to show what should not pass
    ]) == []

    print("all tests passed")
```

The last test above is intentionally invalid as written because `"(1, 010)"` should never be returned. A correct executable version is:

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

    assert normalize(s.ambiguousCoordinates("(123)")) == normalize([
        "(1, 23)",
        "(1, 2.3)",
        "(12, 3)",
        "(1.2, 3)",
    ])

    assert normalize(s.ambiguousCoordinates("(0123)")) == normalize([
        "(0, 123)",
        "(0, 12.3)",
        "(0, 1.23)",
        "(0.1, 23)",
        "(0.1, 2.3)",
        "(0.12, 3)",
    ])

    assert normalize(s.ambiguousCoordinates("(00011)")) == normalize([
        "(0, 0.011)",
        "(0.001, 1)",
    ])

    assert normalize(s.ambiguousCoordinates("(100)")) == normalize([
        "(10, 0)",
    ])

    assert normalize(s.ambiguousCoordinates("(1010)")) == normalize([
        "(1, 0.10)",
        "(10, 10)",
        "(10.1, 0)",
    ])

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `"(123)"` | Basic split and decimal placements |
| `"(0123)"` | Leading zero rules |
| `"(00011)"` | Many invalid zero forms |
| `"(100)"` | Trailing zero rules |
| `"(1010)"` | Mix of integer and decimal candidates |