We had some 2-dimensional coordinates, like "(1, 3)" or "(2, 0.5)". Then, we removed all commas, decimal points, and spaces and ended up with the string s.
"(1, 3)" becomes s = "(13)" and "(2, 0.5)" becomes s = "(205)".Return a list of strings representing all possibilities for what our original coordinates could have been.
Our original representation never had extraneous zeroes, so we never started with numbers like "00", "0.0", "0.00", "1.0", "001", "00.01", or any other number that can be represented with fewer digits. Also, a decimal point within a number never occurs without at least one digit occurring before it, so we never started with numbers like ".1".
The final answer list can be returned in any order. All coordinates in the final answer have exactly one space between them (occurring after the comma.)
Example 1:
Input: s = "(123)" Output: ["(1, 2.3)","(1, 23)","(1.2, 3)","(12, 3)"]
Example 2:
Input: s = "(0123)" Output: ["(0, 1.23)","(0, 12.3)","(0, 123)","(0.1, 2.3)","(0.1, 23)","(0.12, 3)"] Explanation: 0.0, 00, 0001 or 00.01 are not allowed.
Example 3:
Input: s = "(00011)" Output: ["(0, 0.011)","(0.001, 1)"]
Constraints:
4 <= s.length <= 12s[0] == '(' and s[s.length - 1] == ')'.s are digits.Problem Overview: The input is a string like "(123)" where commas, spaces, and decimal points were removed from the original coordinate pair. Your job is to reconstruct every valid coordinate in the form (x, y). Each side may contain a decimal point, but numbers cannot have leading zeros (except "0") or trailing zeros after a decimal.
Approach 1: Brute Force Split and Validate (O(n^3) time, O(n^2) space)
Remove the surrounding parentheses and try every possible split of the string into a left and right part. For each substring, generate all valid numeric representations by optionally inserting a decimal point. Validation follows two rules: integers cannot have leading zeros unless the value is exactly "0", and decimal numbers cannot end with zero. This produces all valid candidates for the left coordinate and all candidates for the right coordinate. Combine every left candidate with every right candidate to form valid coordinate strings. The approach relies heavily on string operations and systematic enumeration of decimal placements.
Approach 2: Dynamic Generation with String Manipulation (O(n^3) time, O(n^2) space)
Instead of generating all substrings first, dynamically build valid numbers while scanning the characters. For each split index, process the left and right substrings independently and construct possible numeric forms directly using string slicing and rule checks. For example, treat the whole substring as an integer candidate, then try inserting a decimal point at each internal position if it doesn't violate the leading or trailing zero constraints. This avoids unnecessary intermediate strings and keeps the validation logic localized. The technique resembles controlled backtracking over decimal placements while enforcing formatting rules.
Recommended for interviews: The brute force split‑and‑validate approach is what most interviewers expect. It clearly demonstrates how you enumerate splits, enforce numeric formatting rules, and combine candidate lists. The dynamic generation variant is cleaner in implementation but conceptually the same complexity. Showing the brute force first proves correctness; explaining how you reduce redundant checks shows deeper string‑handling skill.
This approach involves splitting the string at every possible position to generate potential x and y coordinate pairs, then validating each potential number. The validation checks ensure no extra leading zeros and proper placement of decimal points according to the problem constraints.
The Python solution first strips the parentheses and attempts to split the string at every possible place. For each possible split, it generates all valid decimal representations for both parts and combines them into coordinate pairs.
Time Complexity: O(n^3), where n is the length of the string without parentheses. The combination of each split leads to n^2 pairs, and validating each part could take O(n) time.
Space Complexity: O(n^3), accounts for storing all possible valid coordinates.
This approach entails directly manipulating potential placements of decimal points while adhering to constraints about digits and format validation. It dynamically generates valid representations of left and right parts without separately validating every substring.
The JavaScript solution directly generates valid parts by evaluating each possible division of the number string, and checking inline conditions for valid splitting, thus efficiently producing the valid coordinates.
JavaScript
C#
Time Complexity: O(n^3), due to multiple levels of iterations and validations. Space Complexity: O(n^3), because all possible coordinates are stored.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Brute Force Split and Validate | Time Complexity: O(n^3), where n is the length of the string without parentheses. The combination of each split leads to n^2 pairs, and validating each part could take O(n) time. |
| Dynamic Generation with String Manipulation | Time Complexity: O(n^3), due to multiple levels of iterations and validations. Space Complexity: O(n^3), because all possible coordinates are stored. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Split and Validate | O(n^3) | O(n^2) | Best for clarity. Easy to reason about and commonly expected in interviews. |
| Dynamic Generation with String Manipulation | O(n^3) | O(n^2) | Cleaner implementation when generating decimal placements directly without extra validation passes. |
Ambiguous Coordinates | Live Coding with Explanation | Leetcode - 816 • Algorithms Made Easy • 1,756 views views
Watch 9 more video solutions →Practice Ambiguous Coordinates with our built-in code editor and test cases.
Practice on FleetCode