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:

"(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:

"00"
"001"
"0.0"
"1.0"
".1"

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

"(x, y)"

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

Input and Output

Examples

Example 1:

s = "(123)"

Possible coordinates are:

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

So a valid answer is:

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

Example 2:

s = "(0123)"

Some valid coordinates are:

"(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:

s = "(00011)"

A valid answer is:

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

First Thought: Try Every Split

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

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:

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

But zero rules remove many candidates.

The validation rules are:

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

Algorithm

Remove the outer parentheses:

digits = s[1:-1]

For every split position:

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:

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

Return the answer list.

Generating Valid Numbers

For a digit string part:

If its length is 1, return it:

["0"] or ["5"]

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

"00" -> []
"000" -> []

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

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

"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).

Implementation

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:

digits = s[1:-1]

The helper function generates every valid number for one side:

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

A one-digit number is always valid:

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

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

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:

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

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

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

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

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:

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

Then every valid pair is formatted:

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

Testing

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:

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