LeetCode 816 - Ambiguous Coordinates
The problem gives us a compressed string representation of a 2D coordinate. Originally, the coordinate looked something like "(1, 3)" or "(2, 0.5)", but all commas, spaces, and decimal points were removed. Our task is to reconstruct every possible valid original coordinate pair.
Difficulty: 🟡 Medium
Topics: String, Backtracking, Enumeration
Solution
Problem Understanding
The problem gives us a compressed string representation of a 2D coordinate. Originally, the coordinate looked something like "(1, 3)" or "(2, 0.5)", but all commas, spaces, and decimal points were removed. Our task is to reconstruct every possible valid original coordinate pair.
For example:
"(1, 3)" -> "(13)"
"(2, 0.5)" -> "(205)"
Given the compressed string, we must return all coordinate pairs that could have produced it.
A coordinate consists of two numbers:
(x, y)
Both x and y may be integers or decimals. However, the problem imposes strict formatting rules:
- Numbers cannot contain unnecessary leading zeros.
- Numbers cannot contain unnecessary trailing zeros after a decimal point.
- A decimal number must contain at least one digit before the decimal point.
This means the following are invalid:
"00"
"01"
"1.0"
"0.00"
".5"
But these are valid:
"0"
"0.1"
"10"
"1.23"
The input length is very small:
4 <= s.length <= 12
Since the string is tiny, we can afford to enumerate many possibilities. The challenge is not computational scale, but correctly handling all formatting rules and edge cases involving zeros.
The most important observation is that every valid coordinate comes from splitting the digits into two non-empty parts:
(left_part, right_part)
Then, for each part, we generate all valid numeric representations by optionally inserting a decimal point.
Several edge cases can easily break a naive implementation:
- Numbers with leading zeros like
"012" - Decimal numbers ending in zero like
"1.20" - Strings consisting entirely of zeros like
"000" - Single-digit numbers, which are always valid
- Numbers beginning and ending with zero, where almost all decimal placements become invalid
The problem guarantees that the input contains only digits surrounded by parentheses, so we never need to validate characters.
Approaches
Brute Force Approach
The brute-force idea is to try every possible way to reconstruct the original string.
We could:
- Remove the outer parentheses.
- Split the remaining digits into every possible left and right substring.
- For each substring, try every possible decimal point insertion.
- Validate whether the generated number follows all formatting rules.
- Combine all valid left and right numbers into coordinate strings.
This works because every valid answer must come from some split position and some decimal placement.
However, a naive brute-force implementation repeatedly constructs invalid strings and performs unnecessary checks. Without carefully encoding the formatting rules, the implementation becomes messy and error-prone.
Even though the constraints are small enough that brute force technically passes, we can design a cleaner and more systematic solution.
Key Insight
The key insight is that each substring can independently generate all valid numeric representations.
For a substring like "123":
"123"is valid"1.23"is valid"12.3"is valid
But for "012":
"012"is invalid because of leading zeros"0.12"is valid"01.2"is invalid
Instead of generating arbitrary strings and validating later, we can directly generate only valid numbers.
This leads to a clean helper function:
generateCandidates(substring)
This helper returns every valid representation of that substring.
Then the full solution becomes:
- Split the digits into left and right parts.
- Generate all valid left numbers.
- Generate all valid right numbers.
- Combine them.
Because the input is tiny, this enumeration approach is fully efficient.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n^3) | O(n^3) | Tries all splits and decimal placements with repeated validation |
| Optimal | O(n^3) | O(n^3) | Generates only valid numeric forms directly |
Algorithm Walkthrough
- Remove the outer parentheses from the input string.
If the input is "(123)", we work with:
"123"
- Iterate through every possible split position.
For a string of length n, the split index ranges from 1 to n - 1.
Example:
"123"
Possible splits:
"1" | "23"
"12" | "3"
- For each substring, generate all valid numeric representations.
We create a helper function that handles one substring.
The helper first checks whether the entire substring is a valid integer representation.
Rules:
- Single digit numbers are always valid
- Multi-digit integers cannot start with
'0'
- Generate decimal representations.
For every possible decimal point position:
left = s[:i]
right = s[i:]
The decimal number is:
left + "." + right
It is valid only if:
- The integer part does not have leading zeros unless it is exactly
"0" - The fractional part does not end with
'0'
- Combine valid left and right candidates.
For every valid left number and every valid right number:
"(" + left + ", " + right + ")"
Add the result to the answer list. 6. Return the completed list.
Why it works
Every valid coordinate must come from exactly one split position between the left and right coordinates. For each side, every valid numeric representation is generated exactly once by the helper function. Since invalid representations are filtered using the formatting rules, the algorithm produces all valid coordinates and no invalid ones.
Python Solution
from typing import List
class Solution:
def ambiguousCoordinates(self, s: str) -> List[str]:
digits = s[1:-1]
def generate_candidates(part: str) -> List[str]:
candidates = []
# Integer form
if len(part) == 1 or part[0] != '0':
candidates.append(part)
# Decimal forms
for i in range(1, len(part)):
integer_part = part[:i]
fractional_part = part[i:]
# Leading zero rule
if len(integer_part) > 1 and integer_part[0] == '0':
continue
# Trailing zero rule
if fractional_part[-1] == '0':
continue
candidates.append(integer_part + "." + fractional_part)
return candidates
result = []
for split_index in range(1, len(digits)):
left_part = digits[:split_index]
right_part = digits[split_index:]
left_candidates = generate_candidates(left_part)
right_candidates = generate_candidates(right_part)
for left in left_candidates:
for right in right_candidates:
result.append(f"({left}, {right})")
return result
The implementation begins by removing the outer parentheses so we can work directly with the digit sequence.
The generate_candidates helper is the core of the solution. It generates every valid representation for a substring. First, it checks whether the substring itself can be used as an integer. Multi-digit integers with leading zeros are rejected.
Next, the helper tries every decimal point insertion. For each split:
integer_part.fractional_part
it validates the formatting rules:
- The integer part cannot have unnecessary leading zeros.
- The fractional part cannot end in zero.
Only valid representations are added to the candidate list.
The main loop iterates through every possible split between the x and y coordinates. Each side independently generates valid representations, and every pair is combined into the final coordinate string.
Go Solution
func ambiguousCoordinates(s string) []string {
digits := s[1 : len(s)-1]
generateCandidates := func(part string) []string {
candidates := []string{}
// Integer form
if len(part) == 1 || part[0] != '0' {
candidates = append(candidates, part)
}
// Decimal forms
for i := 1; i < len(part); i++ {
integerPart := part[:i]
fractionalPart := part[i:]
// Leading zero rule
if len(integerPart) > 1 && integerPart[0] == '0' {
continue
}
// Trailing zero rule
if fractionalPart[len(fractionalPart)-1] == '0' {
continue
}
candidate := integerPart + "." + fractionalPart
candidates = append(candidates, candidate)
}
return candidates
}
result := []string{}
for splitIndex := 1; splitIndex < len(digits); splitIndex++ {
leftPart := digits[:splitIndex]
rightPart := digits[splitIndex:]
leftCandidates := generateCandidates(leftPart)
rightCandidates := generateCandidates(rightPart)
for _, left := range leftCandidates {
for _, right := range rightCandidates {
result = append(result, "("+left+", "+right+")")
}
}
}
return result
}
The Go implementation follows the same logic as the Python solution. Slices are used to extract substrings efficiently. Since Go strings are immutable byte slices, substring operations are straightforward because the input contains only ASCII digits.
The helper function returns a slice of valid representations. The final answer is accumulated using nested loops over left and right candidate slices.
No special integer overflow handling is needed because we never convert strings into numeric values.
Worked Examples
Example 1
Input: "(123)"
After removing parentheses:
digits = "123"
Possible splits:
| Split Index | Left | Right |
|---|---|---|
| 1 | "1" | "23" |
| 2 | "12" | "3" |
For split index 1:
| Part | Candidates |
|---|---|
| "1" | ["1"] |
| "23" | ["23", "2.3"] |
Generated coordinates:
(1, 23)
(1, 2.3)
For split index 2:
| Part | Candidates |
|---|---|
| "12" | ["12", "1.2"] |
| "3" | ["3"] |
Generated coordinates:
(12, 3)
(1.2, 3)
Final result:
["(1, 23)", "(1, 2.3)", "(12, 3)", "(1.2, 3)"]
Example 2
Input: "(0123)"
Digits:
"0123"
Possible splits:
| Split | Left | Right |
|---|---|---|
| 1 | "0" | "123" |
| 2 | "01" | "23" |
| 3 | "012" | "3" |
Split 1:
| Part | Candidates |
|---|---|
| "0" | ["0"] |
| "123" | ["123", "1.23", "12.3"] |
Coordinates:
(0, 123)
(0, 1.23)
(0, 12.3)
Split 2:
| Part | Candidates |
|---|---|
| "01" | ["0.1"] |
| "23" | ["23", "2.3"] |
Coordinates:
(0.1, 23)
(0.1, 2.3)
Split 3:
| Part | Candidates |
|---|---|
| "012" | ["0.12"] |
| "3" | ["3"] |
Coordinate:
(0.12, 3)
Example 3
Input: "(00011)"
Digits:
"00011"
Possible splits:
| Split | Left | Right |
|---|---|---|
| 1 | "0" | "0011" |
| 2 | "00" | "011" |
| 3 | "000" | "11" |
| 4 | "0001" | "1" |
Split 1:
| Part | Candidates |
|---|---|
| "0" | ["0"] |
| "0011" | ["0.011"] |
Coordinate:
(0, 0.011)
Split 4:
| Part | Candidates |
|---|---|
| "0001" | ["0.001"] |
| "1" | ["1"] |
Coordinate:
(0.001, 1)
All other splits produce no valid candidates.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n^3) | There are O(n) splits, each generates O(n) candidates, and combining them may take O(n^2) |
| Space | O(n^3) | The output itself may contain O(n^3) total characters |
The input length is at most 10 digits after removing parentheses, so this complexity is easily manageable.
The dominant cost comes from generating candidate strings and storing all valid coordinate combinations.
Test Cases
from typing import List
class Solution:
def ambiguousCoordinates(self, s: str) -> List[str]:
digits = s[1:-1]
def generate_candidates(part: str) -> List[str]:
candidates = []
if len(part) == 1 or part[0] != '0':
candidates.append(part)
for i in range(1, len(part)):
integer_part = part[:i]
fractional_part = part[i:]
if len(integer_part) > 1 and integer_part[0] == '0':
continue
if fractional_part[-1] == '0':
continue
candidates.append(integer_part + "." + fractional_part)
return candidates
result = []
for split_index in range(1, len(digits)):
left_candidates = generate_candidates(digits[:split_index])
right_candidates = generate_candidates(digits[split_index:])
for left in left_candidates:
for right in right_candidates:
result.append(f"({left}, {right})")
return result
solution = Solution()
# Example 1
assert sorted(solution.ambiguousCoordinates("(123)")) == sorted([
"(1, 23)",
"(1, 2.3)",
"(12, 3)",
"(1.2, 3)"
])
# Example 2
assert sorted(solution.ambiguousCoordinates("(0123)")) == sorted([
"(0, 123)",
"(0, 12.3)",
"(0, 1.23)",
"(0.1, 23)",
"(0.1, 2.3)",
"(0.12, 3)"
])
# Example 3
assert sorted(solution.ambiguousCoordinates("(00011)")) == sorted([
"(0, 0.011)",
"(0.001, 1)"
])
# Single valid split with zeros
assert sorted(solution.ambiguousCoordinates("(100)")) == sorted([
"(10, 0)"
])
# Leading zero decimal only
assert sorted(solution.ambiguousCoordinates("(010)") ) == sorted([
"(0, 10)",
"(0.1, 0)"
])
# Minimal length input
assert sorted(solution.ambiguousCoordinates("(11)")) == sorted([
"(1, 1)"
])
# Multiple decimal possibilities
assert sorted(solution.ambiguousCoordinates("(1234)")) == sorted([
"(1, 234)",
"(1, 2.34)",
"(1, 23.4)",
"(12, 34)",
"(12, 3.4)",
"(1.2, 34)",
"(1.2, 3.4)",
"(123, 4)",
"(1.23, 4)"
])
# All zeros
assert sorted(solution.ambiguousCoordinates("(0000)")) == sorted([
"(0, 0.0)",
"(0.0, 0)"
])
| Test | Why |
|---|---|
"(123)" |
Basic case with multiple valid decimal placements |
"(0123)" |
Tests leading zero handling |
"(00011)" |
Tests combinations of multiple zeros |
"(100)" |
Ensures trailing zero decimals are rejected |
"(010)" |
Verifies decimal generation after leading zero |
"(11)" |
Smallest meaningful input |
"(1234)" |
Larger enumeration case |
"(0000)" |
Extreme zero-heavy scenario |
Edge Cases
Leading Zeros
Inputs like:
"01"
"001"
are tricky because integers with leading zeros are invalid. A naive implementation might incorrectly allow "01" as a valid integer.
The solution handles this by only accepting multi-digit integers when:
part[0] != '0'
Otherwise, the substring may only appear in decimal form like "0.1".
Trailing Zeros in Decimal Numbers
Values like:
"1.0"
"2.30"
must be rejected because the original representation never contained unnecessary trailing zeros.
The implementation checks:
fractional_part[-1] == '0'
If true, that decimal representation is skipped.
Numbers Beginning and Ending with Zero
Substrings like:
"000"
"0001"
are particularly error-prone because most decimal placements become invalid.
For example:
"0001"
cannot become:
"00.01"
"000.1"
because the integer portion would contain leading zeros.
The implementation carefully validates both the integer and fractional parts independently, ensuring that only valid forms such as:
"0.001"
are generated correctly.