Watch 10 video solutions for Ambiguous Coordinates, a medium level problem involving String, Backtracking, Enumeration. This walkthrough by Algorithms Made Easy has 1,756 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |