Get started

Ambiguous Coordinates — Medium Problem & Solution

A 2-D point was written as "(x, y)", for example "(1, 3)" or "(2, 0.5)".

  • Difficulty: Medium
  • Topics: Strings, Backtracking, Enumeration
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A 2-D point was written as "(x, y)", for example "(1, 3)" or "(2, 0.5)". Then every comma, decimal point and space was erased, leaving s — for example "(13)" or "(205)".

Return every point the original string could have been. A number in the original never had extraneous digits: no leading zeros ("00", "01", "001.5" are impossible), no trailing zeros after a decimal point ("1.0", "0.50" are impossible), and a decimal point always had at least one digit on each side (".5" is impossible, "0.5" is fine).

Write each point as "(x, y)" — exactly one space after the comma — and return the list sorted in ascending ASCII order.

Example 1

Input: s = "(123)"
Output: ["(1, 2.3)","(1, 23)","(1.2, 3)","(12, 3)"]

Example 2

Input: s = "(0010)"
Output: ["(0.01, 0)"]
Explanation: `"0, 010"` and `"00, 10"` have leading zeros; `"0.010"` has a trailing zero.

Example 3

Input: s = "(100)"
Output: ["(10, 0)"]

Constraints

  • 4 <= s.length <= 12
  • s[0] == '(' and s[s.length - 1] == ')'
  • the other characters of s are digits

How to solve Ambiguous Coordinates

The two coordinates are independent once the comma position is fixed, so the answer is a union over comma positions of (legal spellings of the left) × (legal spellings of the right).

Approach

  1. Strip the parentheses to get the digit string d.
  2. spell(x): include x if x == "0" or x[0] != '0'. For each i from 1 to len(x) - 1, include x[:i] + "." + x[i:] when the integer part x[:i] is "0" or does not start with 0, and the fraction x[i:] does not end with 0.
  3. For each comma position i, add "(" + a + ", " + b + ")" for all a in spell(d[:i]) and b in spell(d[i:]).
  4. Sort the strings by character code.

Why it works

A spelling is legal exactly when its integer part is canonical (no leading zero unless it is the single digit 0) and its fractional part, if present, is non-empty and does not end in 0 — the checks in spell. Every original point corresponds to one comma position and one spelling on each side, so the enumeration finds all of them once.

Complexity

  • Time — O(n^4) — n comma positions, O(n^2) spelling pairs, O(n) to build each
  • Space — O(n^3) for the output

Pitfalls

  • "0" alone is legal, but "00", "0.0" and "1.0" are not.
  • A part ending in 0 can still be an integer ("10"), just never a decimal.
  • Keep the exact format "(x, y)" with one space after the comma.

Reference solution

Python

from typing import List

def ambiguousCoordinates(s: str) -> List[str]:
    d = s[1:-1]

    def spell(x):
        res = []
        if x == '0' or x[0] != '0':
            res.append(x)
        for i in range(1, len(x)):
            left, right = x[:i], x[i:]
            if (left == '0' or left[0] != '0') and right[-1] != '0':
                res.append(left + '.' + right)
        return res

    out = []
    for i in range(1, len(d)):
        for a in spell(d[:i]):
            for b in spell(d[i:]):
                out.append('(' + a + ', ' + b + ')')
    out.sort()
    return out

JavaScript

var ambiguousCoordinates = function(s) {
    var d = s.substring(1, s.length - 1);
    var spell = function(x) {
        var res = [];
        if (x === '0' || x.charAt(0) !== '0') res.push(x);
        for (var i = 1; i < x.length; i++) {
            var left = x.substring(0, i), right = x.substring(i);
            if ((left === '0' || left.charAt(0) !== '0') && right.charAt(right.length - 1) !== '0') {
                res.push(left + '.' + right);
            }
        }
        return res;
    };
    var out = [];
    for (var i = 1; i < d.length; i++) {
        var as = spell(d.substring(0, i));
        var bs = spell(d.substring(i));
        for (var a = 0; a < as.length; a++) {
            for (var b = 0; b < bs.length; b++) out.push('(' + as[a] + ', ' + bs[b] + ')');
        }
    }
    out.sort();
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 424 strings problems · the whole catalogue

Learn the technique: Strings · Backtracking